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

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

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

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

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

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

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

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

概述

其他人已经给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。因此，除了我的解释，我还将提供一些带有简单打印语句的算法，以说明不同算法类别的复杂性。

首先，你需要对对数有一个大致的了解，你可以从https://en.wikipedia.org/wiki/Logarithm . 自然科学使用e和自然日志。工程弟子将使用log_10（对数基数10），计算机科学家将大量使用log_2（对数基数2），因为计算机是基于二进制的。有时你会看到自然log的缩写为ln（），工程师通常不使用_10，只使用log（），log_2缩写为lg（）。所有类型的对数都以类似的方式增长，这就是为什么它们共享相同的log（n）类别。

当您查看下面的代码示例时，我建议您先查看O（1），然后查看O（n），然后再查看O（n^2）。在你擅长这些之后，再看看其他的。我已经包含了干净的示例和变体，以证明细微的变化仍然可以导致相同的分类。

你可以把O（1）、O（n）、O（logn）等看作是增长的类或类别。有些类别要比其他类别花费更多的时间。这些类别有助于我们对算法性能进行排序。有些随着输入n的增长而增长得更快。下表以数字形式显示了上述增长。在下表中，将log（n）视为log_2的上限。

各种大O类别的简单代码示例：

O（1）-恒定时间示例：

算法1：

算法1打印一次hello，它不依赖于n，所以它总是在恒定的时间内运行，所以它是O（1）。

print "hello";

算法2：

算法2打印hello 3次，但它不取决于输入大小。即使随着n的增长，该算法也将始终只打印hello 3次。也就是说，3是一个常数，所以这个算法也是O（1）。

print "hello";
print "hello";
print "hello";

O（log（n））-对数示例：

算法3-其行为类似于“log_2”

算法3演示了在log_2（n）中运行的算法。注意for循环的后操作将i的当前值乘以2，因此i从1到2到4到8到16到32。。。

for(int i = 1; i <= n; i = i * 2)
  print "hello";

算法4-其行为类似于“log_3”

算法4证明了log_3。注意我从1到3到9到27。。。

for(int i = 1; i <= n; i = i * 3)
  print "hello";

算法5-其行为类似于“log_1.02”

算法5很重要，因为它有助于表明，只要数字大于1，并且结果与自身重复相乘，那么你就在看对数算法。

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O（n）-线性时间示例：

算法6

这个算法很简单，可以打印n次hello。

for(int i = 0; i < n; i++)
  print "hello";

算法7

该算法显示了一种变体，它将打印hello n/2次。n/2=1/2*n。我们忽略1/2常数，看到这个算法是O（n）。

for(int i = 0; i < n; i = i + 2)
  print "hello";

O（n*log（n））-log（n）示例：

算法8

将其视为O（log（n））和O（n）的组合。for循环的嵌套帮助我们获得O（n*log（n））

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

算法9

算法9类似于算法8，但每个循环都允许变化，这仍然导致最终结果为O（n*log（n））

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O（n^2）-n平方示例：

算法10

O（n^2）很容易通过循环的嵌套标准获得。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

算法11

类似于算法10，但有一些变化。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O（n^3）-n立方示例：

算法12

这类似于算法10，但有3个循环而不是2个。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

算法13

类似于算法12，但具有一些仍然产生O（n^3）的变化。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

总结

上面给出了几个直接的例子和变化，以帮助说明可以引入哪些细微的变化，而这些变化实际上不会改变分析。希望它能给你足够的洞察力。

实际上，如果您有一个n个元素的列表，并从该列表中创建一个二叉树（就像在除法和征服算法中一样），您将一直除以2，直到达到大小为1的列表（树叶）。

在第一步，你除以2。然后，您有2个列表（2^1），将每个列表除以2，因此您有4个列表（2*2），然后再进行一次除法，您有8个列表（3^3），依此类推，直到列表大小为1

这给出了一个等式：

n/（2^步）=1<=>n=2^步<=>lg（n）=步

（取每边的lg，lg为对数基数2）

分而治之范式中的算法具有复杂性O（logn）。这里有一个例子，计算你自己的幂函数，

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

从…起http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

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