无法推断出一个表约算法的有效性

Question

我不完全确定 下列表

alt文本http://files.getdropbox.com/u/175564/algTranslation.png

该表提供的大小可以解决的问题在限定时间定在左栏当复杂的算法是给予的大小。

我感兴趣的扣除的表格。

该表显示我，

• O(n)=10米在第二 (这似乎是权力的当前计算机)
• n 是的项目的数目来处理 # 由于Guffa!

我不确定值如何在列O(n*日志(n))已经推导出来的。

1. 您怎么可以推断出的值0.5米 O(n*日志(n))或3000O(n^2)?

Answer 1

我认为，这个表给出了只是一些非常近似图有多大 n 可以为不同类型的复杂性，当你有固定的时间(1秒、1分钟、1小时,1日或1年)。

例如O(n^3):

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

正如你可以看到，号码是 非常 粗略的估计。看来，提交人希望使用漂亮的圆形数字来说明他的观点。

Answer 2

不，n不是数秒钟，它的项目的数目来处理。

O(n)意味着，时间要处理的项目是线性的数量的项目。

O(n2)意味着，时间到proess的项目是相对于对方的数量的项目。如果你双倍的数量项目，处理时间会四次更长的时间。

参见： 大O符号

本表假定，有一个固定的工作量每个项目，尽管大O符号仅指定一个算法的反应一个变化的项目数量，它不会告诉你任何关于多少工作有每项目。

编辑：
值沿x轴表只是近似值，基于假设的工作，每个项目的是一样的。例如价值3000O(n2)圆形广场根本的10万，这是-3162.28.立方根的10万是不200，它~215.44.

在一个真正的situatuon，两个算法很少做同样的工作量每个项目。一个算法O(日志n)通常做更多的工作，每个项目于O(n)的算法为同一目的，但它仍然是比较好，在大多数情况下，因为它扩展了很多更好。

Answer 3

如果你能做到10,000,000的行动每秒，那么当你设置n=500 000人，并计算n*日志(n)=500 000人*log2(500 000人)=500 000人*18=9,000,000行动，这是大约10,000,000的目的"秒的"分类。

同样，n=3 000名你n^2=9,000,000.因此，在每一行操作的数量大致相同。