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

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

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

因为时间复杂度取决于各种参数。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）中的算法的最佳方式如下：

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

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

概述

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

首先，你需要对对数有一个大致的了解，你可以从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中的位数成正比来直观地想到O（log N）。

如果一个操作对输入的每个数字或位执行恒定的时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成比例，而不是与输入的大小成比例；因此是O（log N）而不是O（N）。

如果一个操作做出一系列恒定的时间决定，每个决定将要考虑的输入的大小减半（减少3、4、5…的因子），那么整个过程将花费与输入大小N的对数基2（基3、基4、基5…）成比例的时间，而不是O（N）。

等等

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

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