O(log n) 到底是什么意思？

Question

我正在学习 Big O Notation 运行时间和摊销时间。我理解O(n)线性时间的概念，这意味着输入的大小会成比例地影响算法的增长......例如，二次时间O(n 2 )等也是如此......甚至算法，例如置换生成器，具有O(n!)次，按阶乘增长。

例如，以下函数是O(n)，因为算法的增长与其输入n成比例：

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

类似地，如果有一个嵌套循环，时间将是 O(n 2 )。

但是O(log n)到底是什么？例如，完全二叉树的高度为O(log n)是什么意思？

我确实知道（可能不是很详细）对数是什么，从某种意义上说：log 10 100 = 2，但我不明白如何识别具有对数时间的函数。

Answer 1

我无法理解如何识别具有日志时间的功能。

对数运行时间函数最常见的属性是：

• 选择执行某些操作的下一个元素是几种可能性之一，并且
• 只需要选择一个。

或者

• 执行动作的元素是 n 的数字

这就是为什么，例如，在电话簿中查找人员是 O(log n)。您无需检查电话簿中的每个人才能找到合适的人；取而代之的是，您可以通过根据他们的名字按字母顺序查看的位置来简单地分而治之，并且在每个部分中，您只需要探索每个部分的子集，然后才能最终找到某人的电话号码。

当然，更大的电话簿仍然会花费您更长的时间，但不会像额外大小的比例增加那样快速增长。

---

我们可以扩展电话簿示例来比较其他类型的操作及其运行时间。我们将假设我们的电话簿中有具有唯一名称的企业（“黄页”）和可能没有唯一名称的人员（“白页”）。一个电话号码最多分配给一个人或一个企业。我们还将假设翻到特定页面需要恒定的时间。

以下是我们可能在电话簿上执行的一些操作的运行时间，从最快到最慢：

• O(1)（在最坏的情况下）：给定商家名称所在的页面和商家名称，找到电话号码。
• O(1)（在一般情况下）：给定一个人的名字所在的页面和他们的名字，找到电话号码。
• O(log n)：给定一个人的名字，通过在你还没有搜索到的书的一半左右选择一个随机点来找到电话号码，然后检查这个人的名字是否在那个点。然后重复这个过程大约一半的人的名字所在的书的部分。（这是对人名的二分搜索。）
• O(n)：找出所有电话号码中包含数字“5”的人。
• O(n)：给定一个电话号码，找到那个号码的人或企业。
• O(n log n)：打印机办公室发生了混淆，我们的电话簿的所有页面都以随机顺序插入。通过查看每一页上的名字，然后将该页放在新的空电话簿中的适当位置来修正排序，使其正确。

对于以下示例，我们现在在打印机办公室。电话簿正在等待邮寄给每个居民或企业，每个电话簿上都有一个标签，标识应该邮寄到哪里。每个人或企业都有一本电话簿。

• O(n log n)：我们想要个性化电话簿，所以我们要在他们指定的副本中找到每个人或企业的名字，然后在电话簿中圈出他们的名字，并写一个简短的感谢信感谢他们的惠顾.
• O(n 2 )：办公室出错，每个电话簿中的每个条目的电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。
• O(n · n!)：我们已准备好将电话簿装载到装运码头上。不幸的是，本应装载书籍的机器人出现了故障：它以随机顺序将书籍放到卡车上！更糟糕的是，它将所有书籍装载到卡车上，然后检查它们的顺序是否正确，如果不正确，它会卸载它们并重新开始。（这是可怕的bogo 排序。）
• O(n n )：您修复了机器人，以便它正确加载东西。第二天，您的一位同事对您进行恶作剧，并将装卸平台机器人连接到自动打印系统。每次机器人去加载原始电话簿时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统足够复杂，当遇到要加载的复制书时，机器人不会尝试打印更多的副本，但它仍然必须加载每本已打印的原始和复制书。