数据结构/渐进符号

数据结构
介绍 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小堆 & 最大堆 - 图
哈希表 - 集合 - 权衡

渐进符号

介绍

不存在一种数据结构可以在所有情况下都提供最佳性能。为了选择最适合特定任务的数据结构，我们需要能够判断特定解决方案需要多长时间才能运行。或者更准确地说，你需要能够判断两种解决方案需要多长时间才能运行，然后选择其中较好的一个。我们不需要知道它们需要多少分钟和秒，但我们需要一种方法将算法相互比较。

渐进复杂度是一种使用理想化的（不可比较的）计算工作单位来表达算法成本主要部分的方法。例如，考虑对一副扑克牌进行排序的算法，该算法通过反复搜索牌堆中最低的牌来进行。该算法的渐进复杂度是牌堆中卡片数量的平方。这种二次行为是复杂度公式中的主要项，它表示，例如，如果你将牌堆的大小加倍，那么工作量大约会增加四倍。

成本的确切公式更复杂，并且包含比我们理解算法基本复杂度所需更多的细节。在我们的扑克牌中，在最坏的情况下，牌堆将从反向排序开始，因此我们的扫描必须一直进行到最后。第一次扫描将涉及扫描$52$张牌，下一次扫描将花费$51$张牌，依此类推。因此成本公式是$52+51+\dots +2$。一般来说，让$N$代表卡片数量，公式是$2+\dots +N$，它等于$N\times {\frac {N+1}{2}}-1={\frac {N^{2}+N}{2}}-1={\frac {1}{2}}\times N^{2}+{\frac {1}{2}}\times N-1$。但$N^{2}$项在表达式中占主导地位，而这对于比较算法成本至关重要。（这实际上是一个昂贵的算法；最好的排序算法在亚二次时间内运行。）

渐进地讲，当$N$趋向于无穷大时，$2+3+\dots +N$越来越接近纯二次函数${\frac {1}{2}}\times N^{2}$。在如此抽象的层面上，${\frac {1}{2}}$的常数因子有何不同？因此，该行为被称为$O(n^{2})$。

现在让我们考虑如何比较两种算法的复杂度。令 $f(n)$ 是一个算法在最坏情况下的成本，表示为输入大小 $n$ 的函数，而 $g(n)$ 是另一个算法的成本函数。例如，对于排序算法，$f(10)$ 和 $g(10)$ 将表示算法对包含 $10$ 个项目的列表所采取的最大步骤数。如果对于所有 $n\geq 0$ 的值，$f(n)$ 小于或等于 $g(n)$，则复杂度函数为 $f$ 的算法严格来说更快。但是，总的来说，我们对计算成本的关注是针对大输入的情况；所以，比较 $f(n)$ 和 $g(n)$ 在 $n$ 的小值上的意义不如比较 $f(n)$ 和 $g(n)$ 在超过某个阈值的 $n$ 上的意义更大。

请注意，我们一直在讨论算法性能的界限，而不是给出确切的速度。对一组牌进行排序（使用我们简单的二次算法）所需的实际步骤数将取决于牌的初始顺序。执行每个步骤的实际时间将取决于我们的处理器速度、处理器缓存的状态等等。在具体的细节上非常复杂，而且与算法的本质无关。

O 符号

定义

O (读作大O) 是表达算法运行时间上界的正式方法。它是衡量算法完成可能需要的最长时间的指标。我们可以假设它代表程序的“最坏情况”。

更正式地说，对于非负函数，$f(n)$ 和 $g(n)$，如果存在一个整数 $n_{0}$ 和一个常数 $c>0$，使得对于所有整数 $n>n_{0}$，$f(n)\leq cg(n)$，那么 $f(n)$ 是 $(g(n))$ 的大 O。这记作 $f(n)=O(g(n))$。如果绘制图表，$g(n)$ 充当您正在分析的曲线 $f(n)$ 的上限。

注意，如果 $f$ 只能取有限值（通常情况下应该如此），那么这个定义意味着存在一个常数 $C$（可能大于 $c$），使得对于所有 $n$ 的值，$f(n)\leq Cg(n)$。$C$ 的一个合适的值是 $c$ 和 $\max _{1\leq n\leq n_{0}}{\frac {f(n)}{g(n)}}$ 的最大值。

理论示例

那么，让我们举一个 Big-O 的例子。假设 $f(n)=2n+8$，并且 $g(n)=n^{2}$。我们能否找到一个常数 $n_{0}$，使得 $2n+8\leq n^{2}$？数字 $4$ 在这里有效，得出 $16\leq 16$。对于任何大于 $4$ 的数字 $n$，这个方法仍然有效。由于我们试图将这个方法推广到 $n$ 的较大值，而较小的值 $\{1,2,3\}$ 不那么重要，我们可以说 $f(n)$ 通常比 $g(n)$ 快；也就是说，$f(n)$ 受 $g(n)$ 限制，并且始终小于它。

因此可以说 $f(n)$ 在 $O(n^{2})$ 时间内运行："f-of-n 在 Big-O of n-squared 时间内运行"。

为了找到上界 - Big-O 时间 - 假设我们知道 $f(n)$ 等于（准确地）$2n+8$，我们可以采取一些捷径。例如，我们可以从运行时间中移除所有常数；最终，在 $n$ 的某个值时，它们变得无关紧要。这使得 $f(n)=2n$。同样，为了方便比较，我们删除常数乘数；在本例中为 $2$。这使得 $f(n)=n$。也可以说 $f(n)$ 在 $O(n)$ 时间内运行；这使我们能够对估计值设定更紧密的（更接近的）上界。

实际例子

$O(n)$：将包含 $n$ 个项目的列表打印到屏幕上，每个项目只查看一次。

$O(\log _{2}{n})$：取一个包含 $n$ 个项目的列表，将其重复地减半，直到只剩下一个项目。

$O(n^{2})$：取一个包含 $n$ 个项目的列表，并将每个项目与其他所有项目进行比较。

大Ω符号

对于非负函数，$f(n)$ 和 $g(n)$，如果存在整数 $n_{0}$ 和常数 $c>0$ 使得对于所有整数 $n>n_{0}$，$f(n)\geq cg(n)$，那么 $f(n)$ 是 $\Omega (g(n))$。这表示为 $f(n)=\Omega (g(n))$.

这与大O符号的定义几乎相同，区别在于 $f(n)\geq cg(n)$，这使得 $g(n)$ 成为下界函数，而不是上界函数。它描述了给定数据规模下 **最佳情况**。

Theta 符号

对于非负函数，$f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的 theta 当且仅当 $f(n)=O(g(n))$ 且 $f(n)=\Omega (g(n))$。这表示为 $f(n)=\Theta (g(n))$.

这基本上是在说函数 $f(n)$ 被同一个函数 $g(n)$ 从上方和下方同时限制。

Theta 符号用 Q 表示。

小 o 符号

对于非负函数 $f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的小 o，当且仅当 $f(n)=O(g(n))$，但 $f(n)\neq \Theta (g(n))$。这记为 $f(n)=o(g(n))$。

这表示 Big O 的一个松散的界限版本。 $g(n)$ 从上方进行限制，但它没有从下方进行限制。

小 Omega 符号

对于非负函数，$f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的小 ω 当且仅当 $f(n)=\Omega (g(n))$，但 $f(n)\neq \Theta (g(n))$。这表示为 $f(n)=\omega (g(n))$.

就像小 o 一样，这是大 Ω 的等价形式。 $g(n)$ 是函数 $f(n)$ 的一个松散的下界；它从底部绑定，但不是从顶部绑定。

渐进符号如何与复杂度分析相关联

时间比较不是算法中唯一的问题。还有空间问题。通常，在算法中会注意到时间和空间之间的权衡。渐进符号使您能够进行这种权衡。如果您将算法使用的时间和空间量视为随时间或空间变化的数据的函数（时间和空间通常分别分析），那么您可以分析在向程序引入更多数据时如何处理时间和空间。

这在数据结构中很重要，因为您希望结构在您增加它处理的数据量时能有效地运行。但请记住，对于大量数据有效的算法并不总是对于少量数据简单且有效的。因此，如果您知道您只处理少量数据，并且您担心速度和代码空间，那么可以为一个对大量数据运行状况不佳的函数进行权衡。

一些渐进符号的例子

通常，我们将渐进符号用作一种方便的方法来检查函数在最坏情况下或最佳情况下可能发生的情况。例如，如果您想编写一个函数，它搜索一个数字数组并返回最小的数字

function find-min(array a[1..n])
  let j := $\infty$
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  return j
end

无论数组的大小如何，每次运行 find-min 时，我们都必须初始化 i 和 j 整型变量并在最后返回 j。因此，我们可以将函数的这些部分视为常量并忽略它们。

那么，我们如何使用渐进符号来讨论 find-min 函数呢？如果我们搜索一个包含 87 个元素的数组，那么 for 循环会迭代 87 次，即使我们遇到的第一个元素恰好是最小值。同样地，对于 $n$ 个元素，for 循环会迭代 $n$ 次。因此，我们说该函数在时间 $O(n)$ 内运行。

那么这个函数呢

function find-min-plus-max(array a[1..n])
  // First, find the smallest element in the array
  let j := $\infty$;
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  let minim := j
  
  // Now, find the biggest element, add it to the smallest and
  j := $-\infty$;
  for i := 1 to n:
    j := max(j, a[i])
  repeat
  let maxim := j
  
  // return the sum of the two
  return minim + maxim;
end

find-min-plus-max 的运行时间是多少？ 有两个 for 循环，每个循环都迭代了 $n$ 次，因此运行时间显然是 $O(2n)$。 因为 $2$ 是一个常数，我们可以将其丢弃并将其运行时间写为 $O(n)$。 为什么可以这样做？ 如果你还记得大 O 符号的定义，那么你正在测试其界限的函数可以乘以某个常数。 如果 $f(x)=2x$，我们可以看到如果 $g(x)=x$，那么大 O 条件成立。 因此 $O(2n)=O(n)$。 此规则对于各种渐进符号都是通用的。

数据结构
介绍 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小堆 & 最大堆 - 图
哈希表 - 集合 - 权衡