大O表示法：修订间差异

2025年5月12日 (一) 00:24的最新版本

大O表示法（Big O notation）是计算机科学中用于描述算法时间复杂度和空间复杂度的数学符号。它表示算法在最坏情况下性能的渐进行为，忽略常数因子和低阶项，专注于输入规模增长时算法的增长趋势。

基本概念[编辑 | 编辑源代码]

大O表示法描述的是算法的渐进上界（Asymptotic Upper Bound）。对于函数 $f (n)$ 和 $g (n)$ ，若存在常数 $c > 0$ 和 $n_{0} > 0$ ，使得对所有 $n \geq n_{0}$ ，有 $f (n) \leq c \cdot g (n)$ ，则记作： $f (n) = O (g (n))$

常见复杂度类别[编辑 | 编辑源代码]

以下是几种常见的大O复杂度类别（按效率从高到低排列）：

$O (1)$ — 常数时间
$O (\log n)$ — 对数时间
$O (n)$ — 线性时间
$O (n \log n)$ — 线性对数时间
$O (n^{2})$ — 平方时间
$O (2^{n})$ — 指数时间
$O (n!)$ — 阶乘时间

代码示例[编辑 | 编辑源代码]

常数时间 $O (1)$ [编辑 | 编辑源代码]

无论输入规模如何，执行时间不变。

  
def get_first_element(arr):  
    return arr[0]  # 直接访问数组第一个元素  

# 示例输入  
arr = [1, 2, 3, 4, 5]  
print(get_first_element(arr))  # 输出: 1

线性时间 $O (n)$ [编辑 | 编辑源代码]

执行时间与输入规模成线性关系。

  
def linear_search(arr, target):  
    for num in arr:  
        if num == target:  
            return True  
    return False  

# 示例输入  
arr = [5, 8, 1, 3, 9]  
print(linear_search(arr, 3))  # 输出: True

平方时间 $O (n^{2})$ [编辑 | 编辑源代码]

嵌套循环导致时间复杂度为输入规模的平方。

  
def bubble_sort(arr):  
    n = len(arr)  
    for i in range(n):  
        for j in range(0, n-i-1):  
            if arr[j] > arr[j+1]:  
                arr[j], arr[j+1] = arr[j+1], arr[j]  
    return arr  

# 示例输入  
arr = [64, 34, 25, 12, 22]  
print(bubble_sort(arr))  # 输出: [12, 22, 25, 34, 64]

实际应用场景[编辑 | 编辑源代码]

1. 数据库索引：B树索引的查询复杂度为 $O (\log n)$ ，远优于线性扫描的 $O (n)$ 。 2. 缓存设计：哈希表实现 $O (1)$ 时间复杂度的键值查找。 3. 算法选择：在数据规模较大时，优先选择 $O (n \log n)$ 的排序算法（如快速排序）而非 $O (n^{2})$ 的冒泡排序。

常见误区[编辑 | 编辑源代码]

忽略常数因子：大O表示法不比较 $100 n$ 和 $5 n^{2}$ 的具体值，而是关注增长趋势。
混淆最坏与平均情况：快速排序的平均复杂度是 $O (n \log n)$ ，但最坏情况下是 $O (n^{2})$ 。

进阶分析[编辑 | 编辑源代码]

递归算法的复杂度[编辑 | 编辑源代码]

以斐波那契数列的递归实现为例：

  
def fibonacci(n):  
    if n <= 1:  
        return n  
    return fibonacci(n-1) + fibonacci(n-2)  # 时间复杂度 O(2ⁿ)

递归树分析显示其时间复杂度为 $O (2^{n})$ ，可通过动态规划优化至 $O (n)$ 。

总结[编辑 | 编辑源代码]

大O表示法是衡量算法效率的核心工具，帮助开发者预估算法在不同数据规模下的性能表现。理解并应用大O分析，能有效指导算法选择与优化。

@@ 第1行： / 第1行： @@
 {{DISPLAYTITLE:大O表示法}}
+'''大O表示法'''（Big O notation）是[[计算机科学]]中用于描述[[算法]]时间复杂度和空间复杂度的数学符号。它表示算法在最坏情况下性能的渐进行为，忽略常数因子和低阶项，专注于输入规模增长时算法的增长趋势。
-'''大O表示法'''（Big O notation）是计算机科学中用于描述算法'''时间复杂度'''和'''空间复杂度'''的数学符号。它表示算法在最坏情况下运行时所需的资源（时间或空间）随输入规模增长的变化趋势，忽略常数因子和低阶项，专注于算法的'''渐进性能'''。
+== 基本概念 ==
+大O表示法描述的是算法的'''渐进上界'''（Asymptotic Upper Bound）。对于函数 <math>f(n)</math> 和 <math>g(n)</math>，若存在常数 <math>c > 0</math> 和 <math>n_0 > 0</math>，使得对所有 <math>n \geq n_0</math>，有 <math>f(n) \leq c \cdot g(n)</math>，则记作：
+<math>f(n) = O(g(n))</math>
-== 基本概念 ==
+=== 常见复杂度类别 ===
+以下是几种常见的大O复杂度类别（按效率从高到低排列）：
-大O表示法用于量化算法的效率，通常关注以下两种复杂度：
+* <math>O(1)</math> — 常数时间
-* '''时间复杂度'''：算法执行所需的时间与输入规模的关系。
+* <math>O(\log n)</math> — 对数时间
-* '''空间复杂度'''：算法执行所需的内存与输入规模的关系。
+* <math>O(n)</math> — 线性时间
+* <math>O(n \log n)</math> — 线性对数时间
+* <math>O(n^2)</math> — 平方时间
+* <math>O(2^n)</math> — 指数时间
+* <math>O(n!)</math> — 阶乘时间
-=== 数学定义 ===
+<mermaid>
-给定函数 <math>T(n)</math> 表示算法的时间复杂度，若存在常数 <math>c > 0</math> 和 <math>n_0 > 0</math>，使得对所有 <math>n \geq n_0</math> 有：
+graph LR
-<math>T(n) \leq c \cdot f(n)</math>
+    A[O(1)] --> B[O(log n)]
-则称 <math>T(n)</math> 是 <math>O(f(n))</math>。
+    B --> C[O(n)]
+    C --> D[O(n log n)]
+    D --> E[O(n²)]
+    E --> F[O(2ⁿ)]
+    F --> G[O(n!)]
+</mermaid>
-=== 常见复杂度分类 ===
+== 代码示例 ==
-以下是一些常见的大O复杂度（按效率从高到低排序）：
+=== 常数时间 <math>O(1)</math> ===
-* <math>O(1)</math>：常数时间
+无论输入规模如何，执行时间不变。
-* <math>O(\log n)</math>：对数时间
-* <math>O(n)</math>：线性时间
-* <math>O(n \log n)</math>：线性对数时间
-* <math>O(n^2)</math>：平方时间
-* <math>O(2^n)</math>：指数时间
-* <math>O(n!)</math>：阶乘时间
-<mermaid>
+<syntaxhighlight lang="python">
-graph LR
+def get_first_element(arr):
-    A[O(1)] --> B[O(log n)]
+     return arr[0]  # 直接访问数组第一个元素
-    B --> C[O(n)]
-    C --> D[O(n log n)]
-     D --> E[O(n²)]
-    E --> F[O(2ⁿ)]
-    F --> G[O(n!)]
-</mermaid>
-== 代码示例 ==
+# 示例输入
+arr = [1, 2, 3, 4, 5]
+print(get_first_element(arr))  # 输出: 1
+</syntaxhighlight>
-=== 常数时间 O(1) ===
+=== 线性时间 <math>O(n)</math> ===
-以下代码无论输入规模如何，执行时间不变：
+执行时间与输入规模成线性关系。
-<syntaxhighlight lang="python">
-def get_first_element(arr):
-    return arr[0]  # 直接访问数组第一个元素
-</syntaxhighlight>
-=== 线性时间 O(n) ===
+<syntaxhighlight lang="python">
-以下代码的执行时间与输入规模成正比：
+def linear_search(arr, target):
-<syntaxhighlight lang="python">
+     for num in arr:
-def find_max(arr):
+         if num == target:
-    max_val = arr[0]
+             return True
-     for num in arr:  # 遍历整个数组
+     return False
-         if num > max_val:
-             max_val = num
-     return max_val
-</syntaxhighlight>
-=== 平方时间 O(n²) ===
+# 示例输入
-以下代码的执行时间与输入规模的平方成正比：
+arr = [5, 8, 1, 3, 9]
-<syntaxhighlight lang="python">
+print(linear_search(arr, 3))  # 输出: True
-def print_pairs(arr):
+</syntaxhighlight>
-    for i in arr:      # 外层循环
-        for j in arr:  # 内层循环
-            print(i, j)
-</syntaxhighlight>
-== 实际应用案例 ==
+=== 平方时间 <math>O(n^2)</math> ===
+嵌套循环导致时间复杂度为输入规模的平方。
-=== 案例1：搜索算法 ===
+<syntaxhighlight lang="python">
-* '''线性搜索'''：<math>O(n)</math>，因为最坏情况下需要检查所有元素。
+def bubble_sort(arr):
-* '''二分搜索'''：<math>O(\log n)</math>，因为每次迭代将搜索范围减半。
+    n = len(arr)
+    for i in range(n):
+        for j in range(0, n-i-1):
+            if arr[j] > arr[j+1]:
+                arr[j], arr[j+1] = arr[j+1], arr[j]
+    return arr
-=== 案例2：排序算法 ===
+# 示例输入
-* '''冒泡排序'''：<math>O(n^2)</math>，因为嵌套循环比较所有元素对。
+arr = [64, 34, 25, 12, 22]
-* '''归并排序'''：<math>O(n \log n)</math>，因为采用分治策略递归拆分和合并。
+print(bubble_sort(arr))  # 输出: [12, 22, 25, 34, 64]
+</syntaxhighlight>
-== 复杂度分析技巧 ==
+== 实际应用场景 ==
+. '''数据库索引'''：B树索引的查询复杂度为 <math>O(\log n)</math>，远优于线性扫描的 <math>O(n)</math>。
+. '''缓存设计'''：哈希表实现 <math>O(1)</math> 时间复杂度的键值查找。
+. '''算法选择'''：在数据规模较大时，优先选择 <math>O(n \log n)</math> 的排序算法（如快速排序）而非 <math>O(n^2)</math> 的冒泡排序。
-. '''忽略常数项'''：<math>O(2n)</math> 简化为 <math>O(n)</math>。
+== 常见误区 ==
-. '''取最高阶项'''：<math>O(n^2 + n)</math> 简化为 <math>O(n^2)</math>。
+* '''忽略常数因子'''：大O表示法不比较 <math>100n</math> 和 <math>5n^2</math> 的具体值，而是关注增长趋势。
-. '''循环嵌套相乘'''：嵌套循环的复杂度是各层循环复杂度的乘积。
+* '''混淆最坏与平均情况'''：快速排序的平均复杂度是 <math>O(n \log n)</math>，但最坏情况下是 <math>O(n^2)</math>。
-. '''递归分析'''：使用递归树或主定理（Master Theorem）计算递归算法复杂度。
-== 常见误区 ==
+== 进阶分析 ==
+=== 递归算法的复杂度 ===
+以斐波那契数列的递归实现为例：
+<syntaxhighlight lang="python">
+def fibonacci(n):
+    if n <= 1:
+        return n
+    return fibonacci(n-1) + fibonacci(n-2)  # 时间复杂度 O(2ⁿ)
+</syntaxhighlight>
+递归树分析显示其时间复杂度为 <math>O(2^n)</math>，可通过[[动态规划]]优化至 <math>O(n)</math>。
-* '''混淆最坏情况和平均情况'''：大O通常描述最坏情况，但某些算法平均性能更好（如快速排序）。
+== 总结 ==
-* '''过度优化'''：有时 <math>O(n^2)</math> 算法在小规模数据上可能比 <math>O(n \log n)</math> 更快（因常数因子更小）。
+大O表示法是衡量算法效率的核心工具，帮助开发者预估算法在不同数据规模下的性能表现。理解并应用大O分析，能有效指导算法选择与优化。
-* '''忽略空间复杂度'''：某些算法（如递归）可能时间高效但占用大量栈空间。
-== 进阶主题 ==
-=== 主定理（Master Theorem） ===
-用于分析分治算法的时间复杂度，形式为：
-<math>T(n) = aT\left(\frac{n}{b}\right) + f(n)</math>
-其中 <math>a \geq 1</math>, <math>b > 1</math>，根据 <math>f(n)</math> 的不同，解分为三种情况。
-=== 平摊分析 ===
-适用于某些操作序列的总成本分摊到单个操作（如动态数组的扩容策略）。
-== 总结 ==
-大O表示法是算法分析的核心工具，帮助开发者：
-* 比较不同算法的效率。
-* 预测算法在大规模数据下的性能。
-* 避免编写低效代码。
-理解并熟练应用大O表示法，是成为优秀程序员的必经之路。
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:算法基础]]