什么是渐近记号（数据结构）？

渐近记号是用于分析算法性能的数学工具，通过理解算法的效率如何随着输入规模的变化而变化来分析。这些记号提供了一种清晰简洁的方式来表达当输入规模趋近于无穷时，算法时间或空间复杂度的行为。

渐近分析的重点在于理解算法复杂度增长的相对速率，而不是直接比较算法。算法的比较是通过抽象掉特定机器的常量和实现细节，而专注于基本趋势来实现的。

如何找到执行操作的时间复杂度或运行时间？

衡量实际运行时间是不可行的。执行任何操作的运行时间都取决于输入的大小。让我们通过一个简单的例子来理解这一点。

假设我们有一个包含五个元素的数组，并且我们想在数组的开头添加一个新元素。为了实现这一点，我们需要将每个元素向右移动，假设每个元素需要一个单位的时间。有五个元素，所以需要五单位时间。假设数组中有 1000 个元素；那么移动就需要 1000 单位时间。这表明时间复杂度取决于输入的大小。

因此，如果输入大小为 n，则 f(n) 是一个关于 n 的函数，表示时间复杂度。

如何计算 f(n)？

对于小型程序，计算 f(n) 的值很容易，但对于大型程序，则不容易。我们可以通过比较它们 f(n) 的值来比较数据结构。我们可以通过比较它们 f(n) 的值来比较数据结构。我们将找出 f(n) 的增长率，因为可能存在一种情况，即一个数据结构对于较小的输入规模更好，但对于较大的输入规模则不然。那么，如何找到 f(n)？

让我们看一个简单的例子。

f(n) = 5n² + 6n + 12

其中 n 是执行的指令数，它取决于输入的大小。

当 n=1 时

% of running time due to 5n2 = (5/5+6+12) * 100 = 21.74%
% of running time due to 6n = (6/5+6+12) * 100 = 26.09%
% of running time due to 12 = (12/5+6+12) * 100 = 52.17%

从上面的计算可以看出，大部分时间都花在了 12 上。但我们必须找到 f(n) 的增长率，我们不能说 12 花费了最多的时间。让我们假设不同的 n 值来找到 f(n) 的增长率。

正如我们在上表中观察到的，随着 n 值的增加，5n² 的运行时间增加，而 6n 和 12 的运行时间也减少。因此，我们观察到对于较大的 n 值，二次方项消耗了近 99% 的时间，因为 n² 项贡献了大部分时间，所以我们可以去掉其他两个项。

因此，

f(n) = 5n²

在这里，我们得到了近似的时间复杂度，其结果非常接近实际结果。这种时间复杂度的近似度量称为渐近复杂度。在这里，我们不是计算确切的运行时间；我们正在消除不必要的项，我们只考虑花费大部分时间的项。

在数学分析中，算法的渐近分析是定义其运行时间性能的数学基础的方法。使用渐近分析，我们可以轻松得出算法的平均情况、最佳情况和最坏情况。

它用于数学上计算算法内任何操作的运行时间。

示例：一个操作的运行时间是 x(n)，另一个操作的运行时间计算为 f(n2)。这表示对于第一个操作，随着 n 的增加，运行时间将线性增加；对于第二个操作，运行时间将呈指数级增加。类似地，如果 n 非常小，则两个操作的运行时间将相同。

通常，算法所需的时间分为三种类型

最坏情况：它定义了算法花费大量时间的输入。

平均情况：程序执行需要平均时间。

最佳情况：它定义了算法花费最短时间的输入

渐近记号

用于计算算法运行时间复杂度的常用渐近记号如下

• 大 O 记号 (O)
• 大 Omega 记号 (Ω)
• 大 Theta 记号 (θ)

大 O 记号 (O)

• 大 O 记号是一种渐近记号，它通过提供函数的增长阶数来衡量算法的性能。
• 此记号为函数提供了一个上限，它确保函数永远不会增长得比上限快。因此，它为函数提供了一个最小上限，以便函数永远不会比此上限增长得更快。

这是表示算法运行时间的上界的正式方法。它衡量算法完成操作的最坏情况时间复杂度或最长运行时间。表示如下

例如

如果 f(n) 和 g(n) 是为正整数定义的两个函数，

则 f(n) = O(g(n))，因为 f(n) 是 g(n) 的大 O（或 f(n) 与 g(n) 同阶），如果存在常数 c 和 n₀，使得

这意味着 f(n) 的增长速度不超过 g(n)，或者 g(n) 是 f(n) 的一个上界。在这种情况下，我们计算函数的增长率，这最终计算了函数的最坏时间复杂度，即算法可能表现的最差情况。

让我们通过示例来理解。

示例 1： f(n)=2n+3, g(n)=n

现在，我们需要找出f(n)=O(g(n)) 吗？

要检查 f(n)=O(g(n))，它必须满足给定条件

f(n)<=c.g(n)

首先，我们将 f(n) 替换为 2n+3，将 g(n) 替换为 n。

2n+3 <= c.n

假设 c=5，n=1，则

2*1+3<=5*1

5<=5

对于 n=1，上述条件为真。

如果 n=2

2*2+3<=5*2

7<=10

对于 n=2，上述条件为真。

我们知道对于任何 n 值，它都将满足上述条件，即 2n+3<=c.n。如果 c 的值为 5，则它将满足条件 2n+3<=c.n。我们可以取从 1 开始的任何 n 值，它都将始终满足。因此，我们可以说存在常数 c 和 n₀，使得 2n+3<=c.n 始终成立。因为它满足上述条件，所以 f(n) 是 g(n) 的大 O，或者我们可以说 f(n) 呈线性增长。因此，可以得出结论，c.g(n) 是 f(n) 的上界。其图形表示如下

使用大 O 记号的思想是给出一个特定函数的上限，并最终得出最坏时间复杂度。它保证一个特定函数不会突然以二次或三次方式运行，它在最坏情况下仅以线性方式运行。

大 Omega 记号 (Ω)

• 它基本上描述了最佳情况，这与大 O 记号相反。
• 这是表示算法运行时间的下限的正式方法。它衡量算法完成所需的最短时间或最佳情况时间复杂度。
• 它确定了算法可以运行的最快时间。

如果我们要求算法至少需要一定的时间而不使用上限，我们就使用大 Ω 记号，即希腊字母“omega”。它用于限制大输入尺寸的运行时间增长。

如果 f(n) 和 g(n) 是为正整数定义的两个函数，

则 f(n) = Ω (g(n))，因为 f(n) 是 g(n) 的 Omega（或 f(n) 与 g(n) 同阶），如果存在常数 c 和 n₀，使得

对于所有 n≥n₀ 且 c>0，f(n)>=c.g(n)

让我们考虑一个例子。

如果 f(n) = 2n+3，g(n) = n，

f(n)= Ω (g(n)) 吗？

它必须满足这些条件

f(n)>=c.g(n)

为了检查上述条件，我们首先将 f(n) 替换为 2n+3，将 g(n) 替换为 n。

2n+3>=c*n

假设 c=1

2n+3>=n （对于从 1 开始的任何 n 值，此方程都为真）。

因此，可以证明 g(n) 是 2n+3 函数的“大 omega”。

正如我们在上图中看到的，当 c 的值为 1 时，g(n) 函数是 f(n) 函数的下界。因此，此记号给出了最快的运行时间。但我们对找到最快运行时间不那么感兴趣；我们对计算最坏情况感兴趣，因为我们想为更大的输入检查我们的算法。这是它可能花费的最坏时间，以便我们可以在后续处理中做出进一步的决定。

大 Theta 记号 (θ)

• Theta 记号主要描述平均情况。
• 它表示算法的实际时间复杂度。在实际问题中，算法并不总是表现得最差或最好，算法主要在最坏情况和最佳情况之间波动，这为我们提供了算法的平均情况。
• 当最坏情况和最佳情况的值相同时，主要使用大 Theta 记号。
• 这是表示算法运行时间的上限和下限的正式方法。

让我们从数学上理解大 Theta 记号

设 f(n) 和 g(n) 是 n 的函数，其中 n 是执行程序所需的步数，则

f(n)= θg(n)

当满足以下条件时，上述条件才成立

其中函数由两个极限（即上限和下限）约束，f(n) 位于两者之间。当 c1.g(n) 小于或等于 f(n) 且 c2.g(n) 大于或等于 f(n) 时，条件 f(n)= θg(n) 才为真。Theta 记号的图形表示如下

让我们考虑一个例子，其中

f(n)=2n+3
g(n)=n

由于 c1.g(n) 应小于 f(n)，因此 c1 必须为 1；而 c2.g(n) 应大于 f(n)，因此 c2 等于 5。c1.g(n) 是 f(n) 的下限，而 c2.g(n) 是 f(n) 的上限。

c1.g(n)<=f(n)<=c2.g(n)

将 g(n) 替换为 n，将 f(n) 替换为 2n+3

c1.n <=2n+3<=c2.n

如果 c1=1, c2=2, n=1

1*1 <=2*1+3 <=2*1

1 <= 5 <= 2 // 对于 n=1，它满足条件 c1.g(n)<=f(n)<=c2.g(n)

如果 n=2

1*2<=2*2+3<=2*2

2<=7<=4 // 对于 n=2，它满足条件 c1.g(n)<=f(n)<=c2.g(n)

因此，我们可以说对于任何 n 值，它都满足条件 c1.g(n)<=f(n)<=c2.g(n)。因此，证明了 f(n) 是 g(n) 的大 Theta。所以，这是提供实际时间复杂度的平均情况。

为什么我们有三种不同的渐近分析？

我们知道，大 Omega 用于最佳情况，大 O 用于最坏情况，大 Theta 用于平均情况。现在，我们将找出线性搜索算法的平均、最坏和最佳情况。

假设我们有一个包含 n 个数字的数组，并且我们想使用线性搜索在数组中查找特定元素。在线性搜索中，每个元素都在每次迭代中与被搜索的元素进行比较。假设如果匹配在第一次迭代中就找到了，那么最佳情况是 Ω(1)；如果元素与最后一个元素匹配，即数组的第 n 个元素，那么最坏情况是 O(n)。平均情况是最佳和最坏情况的中间值，因此它变成 θ(n/1)。常数项可以在时间复杂度中忽略，所以平均情况是 θ(n)。

因此，三种不同的分析在实际函数之间提供了适当的界限。这里，界限意味着我们有上限和下限，它们确保算法仅在这些界限之间运行，即它不会超出这些界限。

常见渐近记号

渐近记号的性质

1. 一般性质

如果 P(n) 是 O(g(n))，则 c*P(n) 也是 O(g(n))，其中 c 是一个常数。

示例

P(n) = 3n²+4 是 O(n²)

那么，6*P(n) = 6(3n²+4) = 18n²+24 也是 O(n²)。

类似地，Ω 和 Θ 记号都满足此性质。

因此，我们可以说，

如果 f(n) 是 Θ(g(n))，则 c*f(n) 也是 Θ(g(n))，其中 c 是一个常数。

如果 f(n) 是 Ω (g(n))，则 c*f(n) 也是 Ω (g(n))，其中 c 是一个常数。

2. 传递性质

如果 p(n) 是 O(g(n)) 且 g(n) 是 O(f(n))，则 p(n) = O(f(n))。

示例

如果 g(n) = n, f(n) = n² 且 p(n)=n³

⇒ n 是 O(n²) 且 n² 是 O(n³)，那么，n 是 O(n³)

类似地，Ω 和 Θ 记号都满足此性质。

我们可以说，

如果 p(n) 是 Θ(g(n)) 且 g(n) 是 Θ(f(n))，则 p(n) = Θ(f(n))。

如果 p(n) 是 Ω (g(n)) 且 g(n) 是 Ω (f(n))，则 p(n) = Ω (f(n))

3. 自反性质

自反性质在理解传递性质后总是很容易理解的。

如果给定了 p(n)，则 p(n) 是 O(p(n))。因为 p(n) 的最大值将是 p(n) 本身！

因此，x = p(n) 和 y = O(p(n)) 总是以自反关系绑定。

示例

g(n) = n² ; O(n²) 即 O(g(n))

类似地，Ω 和 Θ 记号都满足此性质。

我们可以说，

如果给定了 p(n)，则 p(n) 是 Θ(p(n))。

如果给定了 p(n)，则 p(n) 是 Ω (p(n))。

4. 对称性质

如果 g(n) 是 Θ(f(n))，则 f(n) 是 Θ(g(n))。

示例

如果 p(n) = n² 且 f(n) = n²

那么，p(n) = Θ(n²) 且 f(n) = Θ(n²)

请注意，此性质仅适用于 Θ 记号。

5. 反对称性质

如果 g(n) 是 O(f(n))，则 f(n) 是 Ω (g(n))。

示例

如果 g(n) = n, f(n) = n²

那么 n 是 O(n²) 且 n² 是 Ω (n)

此性质仅适用于 Ω 和 O 记号。

6. 更多性质

i. 如果 f(n) = O(g(n)) 且 f(n) = Ω(g(n))，则 f(n) = Θ(g(n))

ii. 如果 f(n) = O(g(n)) 且 d(n)=O(e(n))，则 f(n) + d(n) = O(max( g(n), e(n)))

示例

f(n) = n 即 O(n)

d(n) = n² 即 O(n²)

那么 f(n) + d(n) = n + n² 即 O(n²)

iii. 如果 f(n)=O(g(n)) 且 d(n)=O(e(n))，则 f(n) * d(n) = O( g(n) * e(n))

示例

f(n) = n 即 O(n)

d(n) = n² 即 O(n²)

那么 f(n) * d(n) = n * n² = n³ 即 O(n³)