这个问题已经有了很多好的答案，但我相信我们真的错过了一个重要的答案，那就是图解的答案。

说一个完整的二叉树的高度是O（logn）是什么意思？

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

二进制搜索是一个复杂度为O（logn）的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法，图中显示了我们需要（最多）4次比较才能找到我们在这个16项数据集中搜索的记录。

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

在一张普通纸上绘制对数（n）将生成曲线图，其中曲线的上升速度随着n的增加而减慢：

如果您有一个函数需要：

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.

然后需要log2（n）时间。广义地说，大O符号意味着关系只需要对大n成立，常数因子和小项可以忽略。

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

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

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

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

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

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

因为时间复杂度取决于各种参数。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

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

这两种情况需要O（log n）时间

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O（logn）有点误导，更准确地说，它是O（log2n），即（以2为底的对数）。

平衡二叉树的高度是O（log2n），因为每个节点都有两个（注意log2n中的“两个”）子节点。因此，具有n个节点的树的高度为log2n。

另一个例子是二进制搜索，它的运行时间为O（log2n），因为在每一步中，您都将搜索空间除以2。