"~"表示法对于算法的运行时间意味着什么？

Question

我看到很多像~N^2或~N这样的东西，但我真的不知道"~"是什么意思

Answer 1

表达式前面的波浪号(~)通常表示近似或大致相等。我想这很可能是你遇到的意思。

Answer 2

~表示渐近等于。

在(希望)更容易理解的术语中，它大致意味着是包含常量因子的主导项(与大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

与大0符号相反，你可以用任何东西替换5，而大0只是一个上界，所以你可以使用任何渐近更大的项:

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)