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

我看到很多东西像〜N^2或〜N，但我真的不知道“〜”是什么意思。关于算法的运行时间，“〜”符号是什么意思？

来源

2013-05-06 whitecatgsd

使用SymbolHound搜索的符号网站：http://symbolhound.com/?q=java+~ – Blender 2013-05-06 23:28:07

读一本书塞奇威克？ – 2013-05-06 23:30:17

在这种情况下，这意味着大约。 – BevynQ 2013-05-06 23:30:43

表达式前面的波浪符（〜）通常用于表示大约或大致相等。我认为这很可能是你遇到的意义。

来源

2013-05-06 23:30:58 rad

Thx很多！现在一切都很有意义。 – whitecatgsd 2013-05-06 23:36:33

我想知道“近似”或“大致相当”的数学定义是什么。有些事情让我们确切地说，“这些功能大致相当”或“这些功能不是”。 – Dukeling 2013-05-07 09:05:37

~ 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)

来源

2013-05-07 08:45:18 Dukeling

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

回答

相关问题