php - PHP 数组的大 O

Question

Kendall Hopkins 的回答指出，对于大型数组，php 查找是 O(n)，对于小型数组是恒定时间（意味着 O(1)？！）。他发布了一张图片，其中包含一个图表，该图表显示了恒定数量的查找（100 万）所花费的时间，具体取决于数组的大小。它几乎垂直地开始，然后变平。

从我学到的恒定时间意味着所花费的时间不是数组中元素的函数，这意味着水平图而不是垂直图。我认为他的图表看起来更像 O(log n)，这符合说明 PHP 实现递归哈希表的评论。

我做了自己的测试（使用他的脚本），结果图几乎相同（PHP 5.3.23）。

由于这是一个评价最高的答案，我有点害怕。你能告诉我我是否把这整个 O(x) 弄错了吗？如果是这样，请帮助我。

无论如何：@Kendall Hopkins 感谢您的出色回答！

score 3 · Accepted Answer

您说 Kendall Hopkins 的陈述令人困惑/不正确是正确的（尽管他的其余帖子是一个非常棒的基准测试参考）。

说一个算法对于小输入是 O(1) 是一个相当荒谬的说法。说一个算法是 O(1) 意味着运行时间总是小于一个常数。因此，如果我们将输入空间限制为一个有限集（即“小”输入），那么任何算法都将是 O(1)，因为我们可以从该集中取最长的运行时间作为我们的常数。

他的意思是，对于初始输入范围，增加数组的大小对数组的运行时间几乎没有影响。

如果您想了解更多关于大 O 表示法的信息，那么 [ http://en.wikipedia.org/wiki/Analysis_of_algorithms维基百科页面] 是一个很好的起点。

1 回答 1