什么是“大O”符号的简单英语解释？

Question

什么是“大O”符号的简单英语解释？我更喜欢尽可能少的正式定义和简单的数学。

Answer 1

编辑：快速注意，这几乎肯定会混淆Big O符号（这是一个上限）与Theta符号（这是一个上限和下限）。根据我的经验，这实际上是非学术环境中的典型讨论。对所引起的任何混乱道歉。

用一句话：随着工作规模的增加，完成工作需要多长时间？

显然，只使用“大小”作为输入，“时间”作为输出 - 如果你想谈论内存使用等，同样的想法也适用。

这是一个我们想要干燥的N T恤的例子。我们假设让它们处于干燥位置非常快（即人类的相互作用可以忽略不计）。现实情况并非如此，当然......

• 在外面使用清洗线：假设你有一个无限大的后院，洗涤在O（1）时间内干燥。无论你有多少，它都会得到相同的阳光和新鲜空气，因此尺寸不会影响干燥时间。

• 使用滚筒式烘干机：每次装入10件衬衫，然后一小时后完成。（忽略这里的实际数字 - 它们是无关紧要的。）因此，干燥50件衬衫所需的时间约为干燥10件衬衫的5倍。

• 把所有东西都放在一个通风橱里：如果我们将所有东西放在一个大堆中，只是让一般的温暖去做，那么中间衬衫需要很长时间才能变干。我不想猜测细节，但我怀疑这至少是O（N ^ 2） - 随着你增加洗涤负荷，干燥时间增加得更快。

“大O”符号的一个重要方面是它没有说明给定大小的哪种算法会更快。获取哈希表（字符串键，整数值）与对数组（字符串，整数）。基于字符串，在哈希表或数组中的元素中查找键是否更快？（即对于数组，“找到字符串部分与给定键匹配的第一个元素。”）哈希表通常是摊销的（〜=“平均”）O（1） - 一旦它们被设置，它应该采取同时在100条目表中查找条目，如1,000,000条目表中所示。在数组中查找元素（基于内容而不是索引）是线性的，即O（N） - 平均而言，您将不得不查看一半的条目。

这是否使哈希表比查找数组更快？不必要。如果你有一个非常小的条目集合，一个数组可能会更快 - 你可以在计算你正在查看的哈希码的时间内检查所有字符串。然而，随着数据集变大，哈希表最终会击败数组。