在算法的渐进分析中，我们经常会遇到诸如大O（Big O）、大欧米伽、大西塔以及波浪号这样的术语，它们用于描述算法的性能。今天，我们将深入探讨其中两个符号之间的区别：大O符号和波浪号（~）。
大O符号 (O)
这个符号主要用于描述算法的渐进上界。从数学角度来说，我们可以这样描述它：
> f(n) = O(g(n))
> 如果存在正常数 c 和 n0，使得
> 0 <= f(n) <= c*g(n)
> 对于所有的 n >= n0 都成立
上述符号表明，在 n = n0 这一点，函数 g(n) 的增长开始逐渐超过 f(n)。在算法分析中，我们通常处理的是较大的 n 值，即 n 趋向于无穷大（n→∞）。因此，我们也可以用极限的形式来定义大O符号：
因此，如果上述极限值落在 0, ∞) 的范围内，则 f(n) = O(g(n))。
示例： n2 = O(n3)
> 阅读更多关于 [大O符号 的内容。
波浪号符号（~）
当我们想要对一个复杂的函数进行简单的近似时，就会使用波浪号符号。它的核心作用是简单地忽略低阶项。我们用 ~g(n) 来表示它。如果 f(n) ~ g(n)，这表明当 n 值很大时，f(n)/g(n) 的比值趋向于 1。用数学公式表达如下：
示例：
1. (n – 1/2)(n – 1/3) = n2 – 5n/6 + 1/6 可以写作 ~n2，因为当我们同时除以这两个函数（n2 – 5n/6 + 1/6 和 ~n2）并在 n 趋向于无穷大时求极限，结果会变为 1。
2. 在 AVL 树中， 在我们插入或删除键值之前，首先需要比较并找到键值的位置。在最坏情况下，所需的比较次数为：
> h+1, 其中 h 是树的高度。
> 由于 AVL 树是高度平衡的树，其高度将是 log2n。
因此，我们可以将 h 的值代入表达式，得到：
> log2n+1
我们可以忽略低阶项，从而将其简化为 ~log2n。所以，AVL 树中的比较次数近似为 ~log2n。
关于渐进分析中 ~ 符号的一些重要特性：
- 它遵循 等价关系 的性质。
- 它与 大西塔符号非常相似。它们之间存在细微的差别，即在大西塔符号中，下界和上界对应的常数可以是不同的值；而在波浪号的情况下，我们得到的 f/g 值总是 1 或者趋向于 1。
大O符号与波浪号的区别
大O符号与波浪号的主要区别如下：
波浪号 (~)
—
由于它类似于大西塔符号，它同时定义了算法的上界和下界。
在这里，常数将始终为 1，因为当我们用 f 除以 g 或 g 除以 f 时，结果总是 1。因此，它给出了对算法更精确的近似。
这里，对于同样的时间复杂度，它将是 ~(n3/3)。常数 1/3 在这里没有意义，因为在渐进分析中，我们只关心函数在 n 值很大时的增长情况。
大西塔符号比波浪号符号用得更多，因为在大西塔符号中，我们可以有不同的任意常数，c1 用于上界，c2 用于下界。
它通常定义平均情况。若想获得关于渐进分析的更多见解，请参考以下链接：