algorithm - 关于算法的运行时间，“~”符号是什么意思？

Question

我看到很多东西，比如~N^2 或~N，但我真的不知道“~”是什么意思。

Answer 1

表达式前面的波浪号 (~) 通常用于表示大致或大致等价。我认为这很可能是您遇到的含义。

Answer 2

~表示渐近等于。

在（希望）更易于理解的术语中，它大致意味着包含常数因子的主要术语（与 Big-O 表示法相反，其中常数因子不起作用）。

或者，更一般地说，f(n) ~ g(n)当且仅当f(n)并且g(n)具有相同的主导项（包括常数因子）。

主导项是最大的项，因为 n -> ∞。

一些例子可以更好地解释它：

5n^2 + 10n + 15 ~ 5n^2

I haven't really seen this used, but also valid:
5n^2 + 10n + 15 ~ 5n^2 + 22n + 7

Not valid:
5n^2 + 10n + 15 ~ n^2

与 Big-O 表示法相反，您可以将 替换为5任何东西，而 Big-O 只是一个上限，因此您可以使用任何渐近更大的术语：

5n^2 + 10n + 15 ∈ O(n^2)

The simplest, smallest representation, as above, is preferred, but also valid:
5n^2 + 10n + 15 ∈ O(999999n^2)
5n^2 + 10n + 15 ∈ O(458279n^2 + 3289n + 77)
5n^2 + 10n + 15 ∈ O(n^3)

Not valid:
5n^2 + 10n + 15 ∈ O(999999n)