数据结构笔记之时间复杂度O(n)中的O是什么的缩写，为什么要用O这个字母？
数据结构笔记之时间复杂度O(n)中的O是什么的缩写，为什么要用O这个字母？
code review!
参考笔记
1.数据结构笔记之时间复杂度O(n)中的O是什么的缩写，为什么要用O这个字母？
2.时间复杂度和空间复杂度探究
文章目录
- 数据结构笔记之时间复杂度O(n)中的O是什么的缩写，为什么要用O这个字母？
-
- 1.时间复杂度中的O
-
- 1.1.为什么用`O`？
- 1.2.常见时间复杂度的例子
- 2.某个函数 f(n) 的增长速度
-
- 2.1.增长速度的直观理解
- 2.2.常见增长速度的比较
- 2.3.为什么分析增长速度很重要？
- 3.具体的函数表达式
-
- 3.1.常数时间复杂度 O(1)
- 3.2.对数时间复杂度 O(log n)
- 3.3.线性时间复杂度 O(n)
- 3.4.线性对数复杂度 O(n log n)
- 3.5.二次方时间复杂度 O(n²)
- 3.6.指数时间复杂度 O(2ⁿ)
- 3.7.阶乘时间复杂度 O(n!)
- 4.不同增长速度的直观比较
- 5.常见困惑
-
- 5.1.for循环的时间复杂度
- 5.2.遍历一个数组的时间复杂度和空间复杂度是多少？
- 5.3.C++中基本类型的空间复杂度是多少？
- 5.4.C++的时间复杂度和空间复杂度和栈内存，堆内存有没有关系？
1.时间复杂度中的O
时间复杂度中的 O 是 “Order”（阶） 的缩写，表示算法运行时间或空间占用与输入规模之间的增长关系。它起源于数学中的“大 O 表示法”（Big-O Notation），用于描述函数的渐近行为。
1.1.为什么用O？
-
来源于数学符号
大 O 表示法最早由德国数学家 Paul Bachmann 在 1894 年的数学文献中提出，并由 Edmund Landau 进一步推广，用于描述函数的增长速度。
O 在数学中代表 Order of Magnitude（数量级），表示随着输入规模增大，函数的增长趋势如何。 -
表示一种上界（Upper Bound）
在算法分析中，O(f(n)) 表示某算法的运行时间不会超过某个函数 f(n) 的增长速度（在输入规模很大的情况下）。这非常符合算法复杂度分析的需求。 -
简洁且通用
用一个单一字母 O 表达增长趋势简单明了，避免了复杂的数学符号，让计算机科学家和工程师能更方便地分析和描述算法性能。
1.2.常见时间复杂度的例子
- O(1): 常数时间，比如直接访问数组元素。
- O(n): 线性时间，比如遍历一个长度为 n 的数组。
- O(n²): 二次方时间，比如双重嵌套循环。
- O(log n): 对数时间，比如二分查找。
- O(n log n): 比线性增长稍快，比如快速排序的平均时间复杂度。
总结：O 来自数学中的“大 O 表示法”，表示算法复杂度的增长趋势。它之所以被使用，是因为其来源于数学且能够直观地描述算法性能。
2.某个函数 f(n) 的增长速度
函数 f(n) 的增长速度是指 f(n) 随输入规模 n 增大的变化趋势，也就是描述 f(n) 如何随着 n 增大而增长。它通常用于分析算法的时间复杂度或空间复杂度，帮助我们理解算法在大输入规模下的表现。
2.1.增长速度的直观理解
假设有几个不同的函数 f(n)，我们可以观察它们在输入规模 n 增大时的变化情况：
| f(n) | 增长速度描述 | 举例 (n = 1, 10, 100, 1000) |
|---|---|---|
| O(1) | 常数增长，不随 n 增大而变化 | 1, 1, 1, 1 |
| O(log n) | 对数增长，增长速度极慢 | 0, 1, 2, 3 |
| O(n) | 线性增长，增长速度与 n 成正比 | 1, 10, 100, 1000 |
| O(n log n) | 线性对数增长，比线性略快 | 1, 23, 664, 9966 |
| O(n²) | 二次方增长，增长速度随 n² 增大 | 1, 100, 10000, 1000000 |
| O(2ⁿ) | 指数增长，增长速度非常快 | 2, 1024, 超大, 超级大 |
| O(n!) | 阶乘增长，增速极快，远超指数增长 | 1, 3628800, 超级大, 超级大 |
2.2.常见增长速度的比较
按增长速度从慢到快排序：
- O(1): 常数复杂度，最优增长速度（不随输入规模变化）。
- O(log n): 对数复杂度，增长速度极慢，比如二分查找。
- O(n): 线性复杂度，比如遍历一个数组。
- O(n log n): 线性对数复杂度，比如归并排序或快速排序的平均复杂度。
- O(n²): 二次复杂度，比如双重循环的算法。
- O(2ⁿ): 指数复杂度，比如递归解决子集问题。
- O(n!): 阶乘复杂度，比如全排列或旅行商问题的暴力解法。
2.3.为什么分析增长速度很重要？
- 预测性能：增长速度直接影响算法在大规模数据上的运行时间。
- 选择更优算法：通过比较增长速度，可以选择更高效的算法。例如，面对大规模数据时，选择 O(n log n) 的排序算法明显优于 O(n²) 的排序算法。
- 优化程序：了解增长速度可以帮助我们找出算法瓶颈，优化关键部分的实现。
总结：
函数 f(n) 的增长速度描述了其随输入规模 n 增大的趋势。在算法分析中，我们用大 O 表示法来简化描述，重点关注输入规模很大时的表现。通过比较不同增长速度的函数，我们可以更好地选择和优化算法。
3.具体的函数表达式
如果你想要一些具体函数表达式作为例子，以下是常见的函数增长速度及其具体的数学表示：
3.1.常数时间复杂度 O(1)
- 函数表达式：
( f(n) = 5 ) 或 ( f(n) = 100 )
解释：不管输入规模 ( n ) 的大小，运行时间始终是常数，不会随着 ( n ) 增大而增长。
3.2.对数时间复杂度 O(log n)
- 函数表达式：
( f(n) = \log_2 n ) 或 ( f(n) = \log_{10} n + 3 )
解释：随着 ( n ) 增大，运行时间增长很慢，增长速度是对数级别。例如，二分查找的时间复杂度就是 ( O(\log n) )。
示例：
- 当 ( n = 1 ): ( \log_2(1) = 0 )
- 当 ( n = 10 ): ( \log_2(10) \approx 3.32 )
- 当 ( n = 100 ): ( \log_2(100) \approx 6.64 )
3.3.线性时间复杂度 O(n)
- 函数表达式：
( f(n) = n ) 或 ( f(n) = 3n + 5 )
解释：运行时间与输入