算法第四版中命题证明的～符号是什么意思？

Question

算法第四版中命题证明的～符号是什么意思？

例如书中的顺序查找算法中有句话是:向一个空表插入N个不同的键需要～N^2/2次比较。

Answer 1

例中 向一个空表插入N个不同的键需要～N^2/2次比较，可以理解为【平均情况下，约】。

由于算法存在最好情况和最坏情况下的时间复杂度（如冒泡最好情况下复杂度其实是 O(1)，而快排最坏情况下其实是 O(N^2) 复杂度），因此书中讨论时一般针对平均意义上的时间复杂度，这时用 ~ 符号是很合理的。

Answer 2

这个符号粗略理解是“大约”，但也可以理解成表示更严格意义上的“等阶无穷大”：

$$f(n) \sim g(n):\quad \lim_{n \to \infty} \frac{f(n)}{g(n)}=1$$