0

我不完全确定下表

替代文字 http://files.getdropbox.com/u/175564/algTranslation.png

该表提供了当算法复杂度为给定大小时，可以在左侧列中给出的时间限制内解决的问题大小。

我对表的扣除感兴趣。

这张表告诉我

  • O(n) = 10M 秒（这似乎是当前计算机的能力）
  • n是要处理的项目数#感谢 Guffa！

我不确定如何推导出 O(n * log(n)) 列中的值。

  1. 你如何推断​​出O(n * log(n)) 的值 0.5M 或 O(n^2) 的 3000？
4

3 回答 3

4

不，n 不是秒数，而是要处理的项目数。

O(n) 意味着处理项目的时间与项目的数量成线性关系。

O(n²) 表示处理项目的时间与项目数的平方有关。如果将项目数量增加一倍，则处理时间将延长四倍。

请参阅：大 O 符号

该表假定每个项目的工作量是固定的，尽管大 O 表示法仅指定算法如何对项目数量的变化做出反应，它并没有告诉您每个项目有多少工作量。

编辑：
沿表格 x 轴的值只是基于每个项目的工作相同的假设的近似值。例如，O(n²) 的值 3000 从 1000 万的平方根四舍五入，约为 3162.28。1000 万的立方根不是 200，而是 ~215.44。

在真实情况下，两种算法很少在每个项目上做相同数量的工作。对于相同目的，O(log n) 的算法通常比 O(n) 算法在每个项目上做更多的工作，但在大多数情况下它仍然是可取的，因为它可以更好地扩展。

于 2009-06-28T11:25:39.520 回答
1

如果您每秒可以执行 10,000,000 次操作，那么当您设置 n = 500,000 并计算 n * log(n) = 500,000 * log2(500,000) = 500,000 * 18 = 9,000,000 次操作时，对于“秒”而言，这大约是 10,000,000分类。

同样，当 n = 3,000 时，您会得到 n^2 = 9,000,000。因此，在每一行上，操作的数量大致相同。

于 2009-06-28T16:53:54.140 回答
1

我认为这张表只是给出了一些非常近似的说明，当您有固定时间（1 秒、1 分钟、1 小时、1 天或 1 年）可供您使用时，对于不同类型的复杂性， n可以有多大。

例如 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)

如您所见，这些数字是非常粗略的近似值。似乎作者想用漂亮的整数来说明他的观点。

于 2009-06-28T11:50:13.447 回答