O(log n) 究竟意味着什么？

88250
贡献值 520
贡献次数 1

我目前正在学习 “大 O 记号” 来描述算法的复杂度，比如 O(n) 是线性增长，O(n²) 按平方增长。对于具体一些算法都有固定的复杂度描述，比如置换生成算法是 O(n!) 复杂度，阶乘增长。

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

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

类似地，如果存在嵌套循环，则时间将为 O(n²)。

但究竟什么是 O(log n) 呢？例如，说完整二叉树的高度是 O(log n) 是什么意思？

我知道什么是对数：log₁₀100 = 2，但我要如何才能理解具有对数时间复杂度的算法呢？

答案

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

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

要么

这就是为什么，例如，在电话簿中查找人是 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 ² ）：办公室发生错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的 “0”。取一些白色并删除每个零。
O（n·n！）：我们准备将电话簿加载到装运码头。不幸的是，应该加载书籍的机器人已经变得混乱了：它正在以随机顺序将书籍放到卡车上！更糟糕的是，它将所有书籍加载到卡车上，然后检查它们是否按正确顺序排列，如果没有，则将其卸载并重新开始。（这是可怕的bogo 类型 。）
O（n ⁿ ）：你固定机器人，以便它正确加载东西。第二天，你的一个同事对你进行恶作剧，并将装卸码头机器人连接到自动打印系统。每次机器人装载原始书籍时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统非常复杂，以至于当机器人遇到重复的书籍进行加载时，机器人不会尝试打印更多的副本，但它仍然需要加载已打印的每本原始和重复的书籍。

这个问题已经发布了许多好的答案，但我相信我们真的错过了一个重要的答案 - 即图解答案。

说完整二叉树的高度是 O（log n）是什么意思？

下图描绘了二叉树。注意每个级别如何包含与上面的级别相比的节点数量的两倍（因此是二进制 ）：

二进制搜索是复杂度为O(log n)的示例。假设图 1 中树底层中的节点表示某些已排序集合中的项目。二进制搜索是一种分而治之的算法，该图显示了我们将如何（最多）需要 4 次比较来查找我们在此 16 项数据集中搜索的记录。

假设我们有一个包含 32 个元素的数据集。继续上面的绘图，发现我们现在需要进行 5 次比较才能找到我们要搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，算法的复杂性可以描述为对数阶。

在一张普通纸上绘制log(n) ，将得到一个图表，其中曲线的上升随着n增加而减速：

O(log N)基本上意味着时间呈线性上升，而n呈指数上升。因此，如果它需要1秒到计算10的元件，这将需要2秒，以计算100的元件， 3秒，以计算1000元素，依此类推。

当我们划分并征服算法类型（例如二进制搜索O(log n)时，它是O(log n) 。另一个例子是快速排序，每次我们将数组分成两部分，每次需要O(N)时间来找到一个数据元素。因此它NO(log N)