O（log n）到底是什么意思？

我正在学习大O符号的运行时间和摊销时间。我理解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，但我不知道如何识别具有对数时间的函数。

当前回答

这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。

其他回答

完整的二进制示例是O（ln n），因为搜索结果如下：

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

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

首先，我建议您阅读以下书籍：；

算法（第4版）

下面是一些函数及其预期的复杂性。数字表示语句执行频率。

以下Big-O复杂性图表也取自bigocheatsheet

最后，非常简单的展示展示了它是如何计算的；

剖析程序的语句执行频率。

分析程序的运行时间（示例）。

下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。

二叉树是一种情况，其中大小为n的问题被划分为大小为n/2的子问题，直到我们达到大小为1的问题：

这就是你如何得到O（logn），这是在上面的树上需要完成的工作量，以获得解决方案。

具有O（logn）时间复杂度的常见算法是二进制搜索，其递归关系为T（n/2）+O（1），即在树的每个后续级别上，您将问题分成一半，并执行恒定数量的额外工作。

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

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

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

推荐文章