C 语言中的大 O 记法

17 Mar 2025 | 6 分钟阅读

在 C 语言的数据结构和算法中，我们已经学习了许多算法，并理解了算法的不同方面和目的。我们还研究了算法的复杂度，以及如何分析和计算算法的复杂度。我们计算了算法的时间复杂度和空间复杂度，并得出结论：时间复杂度和空间复杂度较低的算法被评估为最佳算法。我们理解了如何找到算法的最佳情况、最坏情况和平均情况。因此，为了分析所有这些复杂度并表示它们，我们使用了渐近记法的概念，在该概念下有不同类型的表示复杂度的方法。其中一种类型是大 O 记法。

在本节中，我们将讨论大 O 记法，并简要介绍渐近记法及其类型。

什么是渐近记法

这些是用于算法渐近分析的数学符号。术语“渐近”描述了一个变量存在且其值趋向于无穷大的表达式。简而言之，它是一种描述表达式极限行为的方法。因此，使用渐近记法，我们分析算法的复杂度和性能。通过渐近记法，我们在分析后确定并显示复杂度。因此，有三种渐近记法可以用来分析算法的复杂度：

大 O 记法 (O)： 它表示算法运行时间的上界。大 O 记法的作用是计算算法执行所需的最长时间，即它用于计算算法的最坏情况时间复杂度。
Omega 记法 (Ω(n))： 它表示算法运行时间的下界。它用于计算算法完成执行所需的最短时间，即它用于衡量算法的最佳情况时间复杂度。
Theta 记法 (Θ(n))： 它结合了大 O 记法和 Omega 记法的中间特性，因为它表示算法的下界和上界。

因此，这三种渐近记法是最常用的记法，但除了这些之外，还有其他常见的渐近记法，如线性、对数、立方等。

大 O 符号

大 O 记法用于表示算法运行时间的上界，从而衡量算法的最坏情况时间复杂度。它分析和计算算法对于给定输入值执行所需的时间和内存量。

数学上，

对于函数 f(n) 和另一个函数 g(n)，其中两个函数都在某个无界实的（正数）集合上定义。

其中 g(n) 对于所有较大的 n 值都严格为正。可以写成

f(n) = O(g(n))，其中 n 趋向于无穷大 (n → ∞)

但可以发现，n 趋向于无穷大的假设未说明，因此我们可以简单地将上述表达式写为

f(n) = O(g(n))

此处，f 和 g 是从正整数到非负实数的必要函数。

因此，大 O 渐近记法指的是 n 的大值。

大 O 记法的性质

以下讨论了大 O 记法的一些基本性质：

常数乘法
如果 f(n) = c.g(n)，则 O(f(n)) = O(g(n))，其中 c 是非零常数。
求和函数
如果 f(n) = f₁(n) + f₂(n) + -- + f_m(n) 且 f_i(n)≤ f_i+1(n) ∀ i=1, 2,--, m，
则 O(f(n)) = O(max(f1(n), f2(n), --, fm(n)))。
多项式函数
如果 f(n) = a0 + a1.n + a2.n2 + -- + am.nm，
则 O(f(n)) = O(nm)。
对数函数
如果 f(n) = logan 且 g(n)=logbn，
则 O(f(n))=O(g(n))

此处，就大 O 记法而言，所有对数函数都以相同的方式增长。

大 O 记法如何分析算法的运行时间

为了分析算法的性能，我们通常会计算并比较算法的最坏情况运行时间复杂度。O(1) 的阶，称为常数运行时间，被认为是算法最快的运行时间，此时算法所需时间对于不同的输入大小是相同的。然而，常数运行时间是算法的理想运行时间，但很少能实现。这是因为算法的运行时间取决于输入的大小 n。

例如

正如我们所知，算法的运行时间性能取决于输入的大小 n。让我们通过一些数学示例来为不同大小的 n 进行算法的运行时间分析：

n = 20
log (20) = 2.996;
20 = 20;
20 log (20) = 59.9;
20² = 400;
2²⁰ = 1084576;
20! = 2.432902 + 18¹⁸;
n = 10
log (10) = 1;
10 = 10;
10 log (10) = 10;
10² = 100;
2¹⁰ = 1024;
10! = 3628800;

因此，类似地，我们计算算法的运行时间性能。让我们看一些算法示例，并分析这些算法的运行时间：

对于线性搜索，运行时间复杂度为 O(n)。
对于二分搜索，运行时间复杂度为 O(log n)。
对于冒泡排序、选择排序、插入排序、桶排序，运行时间复杂度为 O(n^c)。
对于指数算法，例如汉诺塔，运行时间复杂度为 O(c^n)。
对于堆排序、归并排序，运行时间复杂度为 O(n log n)。

大 O 记法如何分析空间复杂度

确定算法的运行时间和空间复杂度都很重要。因为分析算法的运行时间性能可以了解算法的执行时间，而分析算法的空间复杂度可以了解算法占用的内存空间。因此，为了衡量算法的空间复杂度，需要比较算法的最坏情况空间复杂度性能。

为了确定算法的空间复杂度，需要完成以下两项任务：

任务 1： 需要实现特定算法的程序。

任务 2： 需要知道输入的大小 n，以了解每个项目将占用的内存。

这两个是首先需要完成的重要任务，然后我们才能计算算法的空间复杂度。

算法示例

下面我们列出了一些算法示例及其空间复杂度：

对于线性搜索、冒泡排序、选择排序、堆排序、插入排序和二分搜索，空间复杂度为 O(1)。
对于基数排序，空间复杂度为 O(n+k)。
对于快速排序，空间复杂度为 O(n)。
对于归并排序，空间复杂度为 O(log n)。