如果你在图形计算器或类似的东西上绘制一个对数函数，你会发现它的上升速度非常慢——甚至比线性函数还要慢。

这就是为什么对数时间复杂度算法备受追捧的原因：即使对于真正大的n（例如，假设n＝10^8），它们的性能也超出了可接受的范围。

如果你在图形计算器或类似的东西上绘制一个对数函数，你会发现它的上升速度非常慢——甚至比线性函数还要慢。

这就是为什么对数时间复杂度算法备受追捧的原因：即使对于真正大的n（例如，假设n＝10^8），它们的性能也超出了可接受的范围。

分治算法通常具有运行时间的logn成分。这来自于输入的重复减半。

在二进制搜索的情况下，每次迭代都会丢弃一半的输入。需要注意的是，在Big-O表示法中，log是以2为底的log。

编辑：如上所述，对数基数并不重要，但当推导算法的Big-O性能时，对数因子将来自减半，因此我认为它是基数2。

我一直以来在脑海中想象运行在O（log n）中的算法的最佳方式如下：

如果您将问题大小增加一个乘法量（即将其大小乘以10），则做功仅增加一个加法量。

将此应用于二叉树问题，这样您就有了一个很好的应用程序：如果将二叉树中的节点数加倍，则高度仅增加1（一个加法量）。如果再增加一倍，它仍然只增加了1。（显然，我假设它保持平衡）。这样，当问题规模成倍增加时，你的工作量不会加倍，而只是做了稍微多一点的工作。这就是为什么O（logn）算法非常棒的原因。

我无法理解如何使用日志时间标识函数。

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

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

or

执行操作的元素是n的数字

这就是为什么，例如，在电话簿中查找人是O（logn）。你不需要检查电话簿上的每个人，就能找到合适的人；相反，你可以简单地根据他们的名字的字母顺序进行划分和征服，在每个部分中，你只需要探索每个部分的一个子集，就可以最终找到某人的电话号码。

当然，一本更大的电话簿仍然需要更长的时间，但它的增长速度不会像增加电话簿的比例那样快。

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

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

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（ln n），因为搜索结果如下：

1 2 3 4 5 6 7 8 9 10 11 12

搜索4个会产生3次命中：6次，3次，然后4次。而log2 12=3，这是一个很好的近似值，以多少命中需要。