關於算法的運行時間，「〜」符號是什麼意思？

Question

我看到很多東西像〜N^2或〜N，但我真的不知道「〜」是什麼意思。

Answer 1

表達式前面的波浪符（〜）通常用於表示大約或大致相等。我認爲這很可能是你遇到的意義。

Answer 2

~ means asymptotically equal to。

在（希望）更容易理解的術語中，它大致上意味着占主導地位的常數因子包括（與其中常數因子不起作用的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 

相較於大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)