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

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

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

概述

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

首先，你需要对对数有一个大致的了解，你可以从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";

总结

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

对数

好的，让我们试着完全理解对数到底是什么。

想象一下，我们有一根绳子，把它拴在一匹马身上。如果绳子直接系在马身上，那么马拉离（例如，从人身上）所需的力直接为1。

现在想象绳子绕在一根杆子上。要想脱身的马现在必须用力拉很多倍。次数取决于绳索的粗糙度和杆的大小，但我们假设它会将一个人的力量乘以10（当绳索完全转弯时）。

现在，如果绳子绕一圈，马需要用力拉10倍。如果人类决定让马变得很困难，他可以再次将绳子绕在一根杆子上，使它的力量增加10倍。第三个循环将再次将强度增加10倍。

我们可以看到，对于每个循环，值增加10。获得任何数字所需的圈数称为数字的对数，即我们需要3个柱将你的力量乘以1000倍，需要6个柱将力量乘以1000000。

3是1000的对数，6是1000000的对数（以10为底）。

那么O（log n）实际上是什么意思？

在上面的例子中，我们的“增长率”是O（logn）。每增加一圈，我们的绳子所能承受的力就会增加10倍：

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

现在上面的例子确实使用了基数10，但幸运的是，当我们讨论大o符号时，对数的基数是微不足道的。

现在，让我们假设您正在尝试猜测1-100之间的数字。

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

现在你猜了7次才猜对。但这里的关系是什么？你可以从每一个额外的猜测中猜出最多的项目是什么？

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

使用该图，我们可以看到，如果我们使用二进制搜索来猜测1-100之间的数字，最多需要7次尝试。如果我们有128个数字，我们也可以在7次尝试中猜出数字，但129个数字最多需要8次尝试（与对数相关，这里我们需要7次猜测128个值范围，10次猜测1024个值范围。7是128的对数，10是1024的对数（以2为底））。

注意，我用粗体字“最多”。大O符号总是指更坏的情况。如果你运气好，你可以一次猜出数字，所以最好的情况是O（1），但那是另一回事。

我们可以看到，我们的数据集正在缩小。识别算法是否具有对数时间的一个很好的经验法则是查看数据集在每次迭代后是否按一定顺序收缩

O（n log n）呢？

你最终会遇到一个线性时间O（n log（n））算法。上述经验法则再次适用，但这一次对数函数必须运行n次，例如，将列表的大小减少n次，这在合并排序等算法中发生。

您可以很容易地确定算法时间是否为n log n。寻找一个在列表（O（n））中迭代的外部循环。然后查看是否存在内部循环。如果内部循环在每次迭代时都在切割/减少数据集，则该循环为（O（logn）），因此整个算法为=O（n logn）。

免责声明：绳对数示例摘自W.Sawyer的《数学家的喜悦》一书。

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

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

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

但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？

我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。

我无法理解如何用对数来识别函数时间

对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。

对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。

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