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，但我不知道如何识别具有对数时间的函数。

当前回答

每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。

渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。

因为时间复杂度取决于各种参数。1.物理系统2.编程语言3.编码样式4.还有更多。。。。。。

实际执行时间不是一个很好的分析指标。

相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。因此，执行时间是输入大小的函数。

以下是线性时间算法的示例

线性搜索给定n个输入元素，要搜索数组中的元素，最多需要“n”个比较。换句话说，无论你使用什么编程语言，你喜欢什么编码风格，在什么系统上执行它。在最坏的情况下，它只需要n次比较。执行时间与输入大小成线性比例。

它不仅仅是搜索，无论是什么工作（增量、比较或任何操作），它都是输入大小的函数。

所以当你说任何算法都是O（logn）这意味着执行时间是输入大小n的log倍。

随着输入大小的增加，完成的工作（这里是执行时间）增加。（因此，比例）

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

随着输入大小的增加，所做的工作也会增加，并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。

2018-02-09 05:59:46

其他回答

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

算法（第4版）

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

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

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

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

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

2017-07-02 20:35:42

我想补充一点，树的高度是从根到叶的最长路径的长度，节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。

你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。

2013-12-01 23:52:14

对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。

2010-02-21 20:10:14

我可以补充一些有趣的东西，很久以前我在科尔曼等的书中读过。现在，想象一个问题，我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。

现在，如果你能证明，在你的算法的每一次迭代中，你都切断了这个空间的一部分，这不小于某个极限，这意味着你的算法在O（logN）时间内运行。

我应该指出，我们这里讨论的是相对分数极限，而不是绝对分数极限。二进制搜索是一个经典的例子。在每一步中，我们都会丢掉1/2的问题空间。但二进制搜索并不是唯一的例子。假设，你以某种方式证明了，在每一步中，你至少丢掉了1/128的问题空间。这意味着，您的程序仍然以O（logN）时间运行，尽管比二进制搜索慢得多。这是分析递归算法的一个很好的提示。通常可以证明，在每一步递归都不会使用几个变量，这会导致问题空间中某些分数的截断。

2014-02-04 12:52:03