O（log n）是什么意思？
我目前正在学习Big O Notation运行时间和分期偿还时间。 我理解O（n）线性时间的概念，这意味着输入的大小会按比例影响算法的增长......例如，二次时间O（n2）等也是如此。甚至算法，例如置换生成器，具有O（n！）次，可以通过阶乘增长。
例如，下面的函数是O（n），因为该算法与其输入n成比例增长：
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
同样，如果存在嵌套循环，则时间为O（n2）。
但究竟是O（log n）？ 例如，说完整二叉树的高度是O（log n）是什么意思？
我知道（也许不是很详细）对数是什么，在这个意义上说：log10 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（n2）：办公室出现错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。 采取一些白掉，并删除每个零。
O（n·n！）：我们准备将电话簿加载到发货码头。 不幸的是，本来应该装载书籍的机器人已经不合时宜了：它会随机将书放到卡车上！ 更糟糕的是，它将所有书籍装载到卡车上，然后检查它们是否按正确的顺序排列，如果没有，则卸载它们并重新开始。 （这是可怕的bogo排序 。）
O（nn）：你修复了机器人，以便正确加载东西。 第二天，你的一位同事在你身上扮演一个恶作剧，并将装卸码头机器人连接到自动打印系统。 机器人每次装入原始书籍时，工厂打印机都会重复运行所有电话簿！ 幸运的是，机器人的缺陷检测系统非常复杂，机器人在遇到重复装载的书时不会尝试打印更多副本，但它仍然需要加载已打印的每本原始和重复的书。
这个问题已经发布了很多好的答案，但我相信我们确实错过了一个重要的答案 - 即所说明的答案。
说一个完整的二叉树的高度是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(N)时间来找到一个主元素。 因此它NO(log N)