O（log n）是什么意思？

对数运行时间（O(log n)）本质上意味着运行时间与输入大小的对数成比例增长——例如，如果10个项目最多需要一些时间x,100个项目最多需要2x,10,000个项目最多需要4x，那么它看起来像是O(log n)时间复杂度。

它只是意味着此任务所需的时间随着log（n）的增长而增长（例如：2s表示n=10,4s表示n=100，…）。阅读维基百科关于二进制搜索算法和大O符号的文章以获得更多精度。

完整的二进制示例是O（ln n），因为搜索看起来像这样：

1 2 3 4 5 6 7 8 9 10 11 12

搜索4会得到3个命中：6,3然后是4。log2 12=3，这是一个很好的估计需要多少命中。

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

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

分而治之算法通常对运行时间有一个logn分量。这来自于输入的重复减半。

在二分搜索的情况下，每次迭代都会丢弃一半的输入。应该注意的是，在Big-O符号中，log是log base 2。

编辑：如前所述，对数基数无关紧要，但是在推导算法的Big-O性能时，对数因子将来自减半，因此我将其视为基数2。

如果你有一个函数需要：

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.

然后它需要log₂（n）时间。大O符号，松散地说，意味着该关系只需要对大n为真，并且可以忽略常数因子和较小的项。

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

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

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

你可以直观地想到O（log N），说时间与N中的位数成正比。

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

如果一个操作做出一系列恒定的时间决策，每个决策都将要考虑的输入大小减半（减少3,4,5…），则整个时间将与输入大小N的对数基数2（基数3，基数4，基数5…）成比例，而不是O（N）。

诸如此类。

我无法理解如何识别具有日志时间的函数。

对数运行时函数最常见的属性是：

• 选择要对其执行某些操作的下一个元素是几种可能性之一，并且
• 只需要选择一个。

或

• 执行动作的元素是n的数字

这就是为什么，例如，在电话簿中查找人是O（log n）。你不需要在电话簿中检查每来找到合适的人；相反，你可以简单地根据他们的名字按字母顺序查找来分而治之，在每个部分中，你只需要探索每个部分的一个子集，然后才能最终找到某人的电话号码。

当然，一个更大的电话簿仍然会花费你更长的时间，但它不会像额外大小的比例增加那样快速增长。

我们可以扩展电话簿的例子来比较其他类型的操作和他们运行时间。我们将假设我们的电话簿有企业（“黄页”），其名称可能唯一，人（“白页”）。一个电话号码最多分配给一个人或企业。我们还将假设翻页到特定页面需要恒定的时间。

以下是我们可能在电话簿上执行的一些操作的运行时间，从最快到最慢：

• O（1）（在最坏的情况下）：给定企业名称所在的页面和企业名称，找到电话号码。

• O（1）（一般情况下）：给定一个人的名字所在的页面和他们的名字，找到电话号码。

• O（log n）：给定一个人的名字，在你还没有搜索的那本书的一半内容中随机选一个点，找到电话号码，然后检查这个人的名字是否在那个点上。然后在这本书的一半内容中重复这个过程。

• O（n）：查找所有电话号码包含数字“5”的人。

• O（n）：给定一个电话号码，找到拥有该号码的个人或企业。

• O（n log n）：打印机的办公室出了点问题，电话簿上的所有页都是随机排列的。请先查看每页上的名字，然后将这一页放到空电话簿中合适的位置，这样可以调整顺序。

对于下面的例子，我们现在在打印机的办公室。电话簿正在等待邮寄给每个居民或企业，每个电话簿上都有一个贴纸，表明应该邮寄到哪里。每个人或企业都有一本电话簿。

• O（n log n）：我们想个性化电话簿，所以我们要在他们指定的副本中找到每个人或企业的名字，然后在书中圈出他们的名字，并为他们的赞助写一封简短的感谢信。

• O（n²）：办公室出现错误，电话簿中每一项的电话号码末尾都多了一个0，删除掉所有0。

• O（n·n！）：我们准备将电话簿装入码头。不幸的是，本该装书的机器人出了问题：它正在随机地将书装上卡车！更糟糕的是，它将所有的书装上卡车，然后检查它们的顺序是否正确，如果不正确，它将它们卸下并重新开始。（这就是可怕的bogo排序。）

• O（nⁿ）：你把机器人修好，让它能正常装货。第二天，你的一个同事和你开玩笑，把装货台机器人连接到自动打印系统上。机器人每次装书时，工厂的打印机都会重复运行所有的电话簿！幸运的是，机器人的bug检测系统足够复杂，当机器人遇到要装书的重复时，它不会尝试打印更多的副本，但它仍然必须装入每一本已经打印的原版和副本。

O(log N)基本上意味着时间呈线性增长，而n呈指数增长。因此，如果计算10个元素需要1秒，计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。

当我们进行分而治之类型的算法时，例如二分搜索，它是O(log n)。另一个例子是快速排序，每次我们将数组分成两部分，每次需要O(N)时间来找到一个枢轴元素。因此它N O(log N)

O(log n)是指一个函数（或算法，或算法中的步骤）工作的时间与输入大小的对数成正比（在大多数情况下通常以2为基数，但并非总是如此，无论如何，通过big-O符号*，这是微不足道的）。

对数函数是指数函数的倒数。换句话说，如果您的输入呈指数增长（而不是您通常认为的线性增长），您的函数将呈线性增长。

O(log n)运行时间在任何类型的分治应用程序中都很常见，因为每次你都（理想地）将工作减半。如果在每个划分或征服步骤中，你都在做恒定时间工作（或不是恒定时间的工作，但随着时间增长比O(log n)慢），那么你的整个函数就是O(log n)。很常见的是，每个步骤都需要输入的线性时间；这将相当于总时间复杂度O(n log n)。

二分搜索的运行时间复杂度是O(log n)的一个例子。这是因为在二分搜索中，你总是通过将数组分成两半来忽略后面的每一步输入的一半，并且每一步只关注一半。每一步都是恒定时间，因为在二分搜索中，你只需要将一个元素与你的键进行比较，就可以知道下一步该做什么，而不管你正在考虑的数组在任何时候有多大。所以你大约需要执行log（n）/log（2）步。

合并排序的运行时间复杂度是O(n log n)的一个例子。这是因为你在每一步都将数组分成两半，总共大约有log（n）/log（2）步。然而，在每一步中，你需要对所有元素执行合并操作（无论是对n/2元素的两个子列表进行一次合并操作，还是对n/4元素的四个子列表进行两次合并操作，都是无关紧要的，因为它增加了在每一步中对n个元素执行此操作的必要性）。因此，总复杂度是O(n log n)。

*记住big-O表示法，根据定义，常数无关紧要。同样，对于对数基规则变更，不同基数的对数之间的唯一区别是一个常数因子。

这个问题已经有了很多很好的答案，但我认为我们确实缺少一个重要的答案，即图解答案。

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

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

二进制搜索是复杂度O(log n)的一个例子。假设图1中树底部的节点代表一些排序集合中的项目。二进制搜索是一种分而治之的算法，该图显示了我们最多需要4次比较来找到我们在这16个项目数据集中搜索的记录。

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

在一张普通的纸上绘制log(n)，将导致曲线的上升随着n的增加而减速：

简单地说：在你的算法的每一步，你可以把工作减半。（渐近等价于第三，第四，…）

我总是必须在脑海中可视化一个以O（log n）运行的算法的最佳方法如下：

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

把这个应用到你的二叉树问题上，这样你就有了一个很好的应用：如果你把二叉树中节点的数量翻倍，高度只增加了1（一个加法量）。如果你再翻倍，它仍然只增加了1。（显然，我假设它保持平衡等）。这样，当问题大小乘以时，你的工作不是翻倍，而是只做了稍微多的工作。这就是为什么O（log n）算法很棒的原因。

什么是log_b（n）？

它是在达到大小为1的部分之前，您可以将长度为n的日志重复切割成b等份的次数。

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

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

这就是你得到O（log n）的方式，这是在上面的树上需要完成的工作量，以达到解决方案。

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

但是O（log n）到底是什么？例如，说>完整二叉树的高度是O（log n）是什么意思？

我会把它改写为“完整二叉树的高度是log n”。如果你一步一步地遍历，计算完整二叉树的高度将是O（log n）。

我不明白如何识别一个对数函数时间

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

对于树示例，您可以很容易地看到，当您继续遍历时，降级节点会减少指数数量的元素。查看按名称排序的电话簿的流行示例本质上相当于遍历二叉查找树（中间页是根元素，您可以在每一步推断是向左还是向右）。

如果你正在寻找一个基于直觉的答案，我想为你提供两种解释。

1. 想象一座很高的山，山脚也很宽。要到达山顶，有两条路：一条是专门的路径，绕着山螺旋延伸，到达山顶，另一条是像雕刻一样的小露台，切割出来提供楼梯。现在，如果第一条路在线性时间O（n）到达，第二条路是O（log n）。

2. 想象一个算法，它接受一个整数，n作为输入，并在与n成比例的时间内完成，那么它是O（n）或theta（n），但如果它在与number of digits or the number of bits in the binary representation on number成比例的时间内运行，那么算法在O（log n）或theta（log n）时间内运行。

log x to base b = y是b^y = x的倒数

如果你有一棵深度为d且大小为n的M-ary树，那么：

• 遍历整个树~O（M^d）=O（n）

• 在树中走一条路~O（d）=O（log n to base M）

这两个案例将花费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（log n）时间复杂度，树应该是平衡的，这意味着任何节点子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏的情况下，在树中搜索的时间复杂度可能是O（n）。

您可以查看平衡树，例如AVL tree。这个在插入数据时平衡树，以便在树中搜索时保持（log n）的时间复杂度。

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

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

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

信息技术意味着：

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N,such thatfor all N>N0  "C*g(n) > f(n) > 0" is true.

蚂蚁似乎这个符号大多取自数学。

在这篇文章中，有一句话：D. E. Knuth，《BIG OMICRON AND BIG OMEGA AND BIG THETA》，1976年：

在这里讨论的问题的基础上，我建议的成员以及计算机科学和数学期刊的编辑，采用上面定义的符号，除非有更好的替代方案很快就发现了

。

今天是2016年，但我们仍然使用它。

在数学分析中，它意味着：

  lim (f(n)/g(n))=Constant; where n goes to +infinity

但即使在数学分析中，有时也会使用这个符号来表示“C*g（n）>f（n）>0”。

据我所知，这个符号是由德国数学家朗道（1877-1938）提出的。

我可以举一个for循环的例子，也许一旦掌握了这个概念，也许在不同的上下文中理解它会更简单。

这意味着在循环中，步长呈指数增长。

for (i=1; i<=n; i=i*2) {;}

这个程序的O表示法的复杂性是O（log（n））。让我们尝试手动循环它（n介于512和1023之间（不包括1024）：

step: 1   2   3   4   5    6    7    8     9     10i: 1   2   4   8   16   32   64   128   256   512

虽然n介于512和1023之间，但只进行了10次迭代。这是因为循环中的步骤呈指数增长，因此只需10次迭代即可到达终止。

x的对数（到a的基数）是a^x的反向函数。

这就像说对数是指数的倒数。

现在试着这样看，如果指数增长非常快，那么对数增长（相反）非常慢。

O（n）和O（log（n））之间的差异是巨大的，类似于O（n）和O（a^n）之间的差异（a是常数）。

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

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;elsereturn x*temp*temp;}

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

概览

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

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

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

你可以将O（1），O（n），O（logns）等视为增长的类或类别。有些类别比其他类别需要更多的时间。这些类别有助于为我们提供一种排序算法性能的方法。有些随着输入n的增长而增长得更快。下表以数字方式展示了所说的增长。在下表中，将log（n）视为log_2的上限。

各种Big 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。注意i从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

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

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））-nlog（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个帖子将您的力量乘以1,000,000。

3是1,000的对数，6是1,000,000的对数（以10为基数）。

那么O（log n）到底是什么意思呢？

在上面的例子中，我们的“增长率”是O（log n）。对于每一个额外的循环，我们的绳子可以处理的力是10倍：

Turns | Max Force0   |   11   |   102   |   1003   |   10004   |   10000n   |   10^n

现在上面的例子确实使用了基数10，但幸运的是，当我们谈论大o符号时，日志的基数并不重要。

现在让我们假设你试图猜测1-100之间的数字。

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

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

Guesses | Items1     |   22     |   43     |   84     |   165     |   326     |   647     |   12810    |   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（log n）），因此整体算法=O（n log n）。

免责声明：绳子对数的例子是从W. Sawyer的优秀的数学家的喜悦书中抓取的

实际上，如果你有一个包含n个元素的列表，并从该列表创建一个二叉树（如分治算法），你将继续除以2，直到你达到大小为1的列表（叶子）。

在第一步，你除以2。然后你有2个列表（2^1），你把每个除以2，所以你有4个列表（2^2），你再除以，你有8个列表（2^3），以此类推，直到你的列表大小为1

这给了你一个等式：

#0

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

首先，我推荐你阅读以下书籍；

算法（第4版）

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

下面的Big-O复杂度图也取自bigocheattable

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

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

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

每次我们编写算法或代码时，我们都会尝试分析其渐近复杂性。######

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

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

实际执行时间不是分析的好度量。

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

下面是线性时间算法的一个例子

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

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

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

随着输入大小的增加，完成的工作（这里是执行时间）也会增加。（因此是相称性）

      n      Work2     1 units of work4     2 units of work8     3 units of work

看到输入大小增加所做的工作增加，它是独立于任何机器。如果你试图找出工作单位的价值它实际上依赖于上面指定的参数，它将根据系统和所有内容而改变。

O（logns）是衡量任何代码运行时性能的多项式时间复杂度之一。

我希望你已经听说过二进制搜索算法。

假设您必须在大小为N的数组中找到一个元素。

基本上，代码执行就像NN/2N/4N/8……等

如果你把每个级别所做的所有工作相加，你将得到n（1+1/2+1/4…），这等于O（logns）

大O符号希望对你有帮助！

大O---------------整理--------------复杂度

O(log N)     -Binary search      - logarithmic
O(N)         -Simple search      - Linear
O(N*log N)   -Quicksort          - loglinear
O(2^N)       -recursive          - Exponential
O(N2)        -Selection sort     - directly proportional to the square of the input size.