我正在学习大O符号的运行时间和摊销时间。我理解O（n）线性时间的概念，这意味着输入的大小成比例地影响算法的增长。。。例如，二次时间O（n2）等也是如此。甚至是通过阶乘增长的算法，如置换生成器，其O（n！）次。
例如，以下函数为O（n），因为算法与其输入n成比例增长：
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
类似地，如果存在嵌套循环，时间将为O（n2）。
但O（log n）到底是什么？例如，说一个完整的二叉树的高度是O（log n）是什么意思？
我确实知道（也许不是很详细）对数是什么，从这个意义上说：log10 100=2，但我不知道如何识别具有对数时间的函数。
对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大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是以2为底的log。
编辑：如上所述，对数基数并不重要，但当推导算法的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.
然后需要log2（n）时间。广义地说，大O符号意味着关系只需要对大n成立，常数因子和小项可以忽略。
O（logn）有点误导，更准确地说，它是O（log2n），即（以2为底的对数）。
平衡二叉树的高度是O（log2n），因为每个节点都有两个（注意log2n中的“两个”）子节点。因此，具有n个节点的树的高度为log2n。
另一个例子是二进制搜索，它的运行时间为O（log2n），因为在每一步中，您都将搜索空间除以2。
你可以通过说时间与N中的位数成正比来直观地想到O（log N）。
如果一个操作对输入的每个数字或位执行恒定的时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成比例，而不是与输入的大小成比例；因此是O（log N）而不是O（N）。
如果一个操作做出一系列恒定的时间决定，每个决定将要考虑的输入的大小减半（减少3、4、5…的因子），那么整个过程将花费与输入大小N的对数基2（基3、基4、基5…）成比例的时间，而不是O（N）。
等等
我无法理解如何使用日志时间标识函数。
对数运行时间函数最常见的属性是：
选择下一个要执行某些操作的元素是多种可能性之一，并且只需要选择一个。
or
执行操作的元素是n的数字
这就是为什么，例如，在电话簿中查找人是O（logn）。你不需要检查电话簿上的每个人，就能找到合适的人；相反，你可以简单地根据他们的名字的字母顺序进行划分和征服，在每个部分中，你只需要探索每个部分的一个子集，就可以最终找到某人的电话号码。
当然，一本更大的电话簿仍然需要更长的时间，但它的增长速度不会像增加电话簿的比例那样快。
我们可以扩展电话簿示例，以比较其他类型的操作及其运行时间。我们将假设我们的电话簿中有具有唯一名称的业务（“黄页”）和可能没有唯一名称的人员（“白页”）。电话号码最多分配给一个人或一家公司。我们还将假设翻到特定页面需要恒定的时间。
以下是我们可能在电话簿上执行的一些操作的运行时间，从最快到最慢：
O（1）（在最坏的情况下）：给定企业名称所在的页面和企业名称，找到电话号码。O（1）（在一般情况下）：给定一个人的名字和他们的名字所在的页面，找到电话号码。O（log n）：给定一个人的名字，在书中你还没有搜索到的部分的中途随机抽取一个点，然后检查这个人的名字是否在这个点上，从而找到电话号码。然后在书中人名所在的部分重复这个过程。（这是对人名的二进制搜索。）O（n）：查找电话号码包含数字“5”的所有人。O（n）：给定一个电话号码，找到拥有该号码的人或企业。O（n log n）：打印机的办公室出现了混乱，我们的电话簿上的所有页面都以随机顺序插入。通过查看每一页上的名字，然后将该页放在新的空电话簿中的适当位置，修正顺序，使其正确。
对于以下示例，我们现在在打印机的办公室。电话簿等待邮寄给每位居民或企业，每个电话簿上都有一个标签，标明应该邮寄到哪里。每个人或企业都有一本电话簿。
O（n log n）：我们想让电话簿个性化，所以我们将在他们指定的副本中找到每个人或企业的名字，然后在电话簿中圈出他们的名字，并为他们的惠顾写一封简短的感谢信。O（n2）：办公室发生了一个错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。取出一些白色，去掉每个零。O（n·n！）：我们准备好把电话簿装到码头上了。不幸的是，原本要装书的机器人已经失控了：它正在把书按随机顺序放在卡车上！更糟糕的是，它把所有的书都装到卡车上，然后检查它们的顺序是否正确，如果不正确，它就把它们卸下来，重新开始。（这是可怕的bogo类型。）O（nn）：你把机器人修好，这样它就能正确地装载东西。第二天，你的一个同事对你开了个玩笑，把装卸台机器人连接到自动打印系统上。每次机器人去装载一本原版书时，工厂打印机都会对所有的电话簿进行重复打印！幸运的是，机器人的错误检测系统足够复杂，当它遇到要加载的复制书时，它不会尝试打印更多的副本，但它仍然必须加载已打印的每一本原始和复制书。
O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。
当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）
O（logn）指的是一个函数（或算法，或算法中的步骤），其工作时间与输入大小的对数成正比（大多数情况下通常以2为基数，但并不总是以2为底，在任何情况下，通过big-O符号*，这都是无关紧要的）。
对数函数是指数函数的倒数。换句话说，如果您的输入呈指数增长（而不是通常认为的线性增长），则函数呈线性增长。
O（logn）运行时间在任何一种分而治之的应用程序中都很常见，因为（理想情况下）每次都会将工作减半。如果在每一个除法或征服步骤中，你都在做恒定时间的工作（或不是恒定时间的，但随着时间的增长比O（log n）慢），那么你的整个函数就是O（log）。相当常见的是，每个步骤都需要输入线性时间；这将相当于O（n log n）的总时间复杂度。
二进制搜索的运行时间复杂性是O（logn）的一个例子。这是因为在二进制搜索中，通过将数组分成两半，并且每一步只关注一半，您总是忽略后面每一步的一半输入。每一步都是恒定的时间，因为在二进制搜索中，您只需要将一个元素与关键字进行比较，就可以确定下一步要做什么，而不管您考虑的数组在任何时候都有多大。因此，大约执行log（n）/log（2）步。
合并排序的运行时间复杂性是O（n log n）的一个例子。这是因为每一步都将阵列一分为二，总共约为log（n）/log（2）步。然而，在每一步中，您都需要对所有元素执行合并操作（无论是对n/2个元素的两个子列表执行一次合并操作，还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的，因为这增加了每一步对n个元素执行合并的必要性）。因此，总复杂度为O（n log n）。
*记住，根据定义，big-O表示法并不重要。同样，通过改变对数的基数规则，不同基数的对数之间的唯一差异是一个常数因子。
这个问题已经有了很多好的答案，但我相信我们真的错过了一个重要的答案，那就是图解的答案。
说一个完整的二叉树的高度是O（logn）是什么意思？
下图描述了一个二叉树。请注意，与上面的级别相比，每个级别包含的节点数量是两倍（因此是二进制的）：
二进制搜索是一个复杂度为O（logn）的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法，图中显示了我们需要（最多）4次比较才能找到我们在这个16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的图，发现我们现在需要5次比较才能找到我们正在搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，该算法的复杂性可以用对数级数来描述。
在一张普通纸上绘制对数（n）将生成曲线图，其中曲线的上升速度随着n的增加而减慢：
我一直以来在脑海中想象运行在O（log n）中的算法的最佳方式如下：
如果您将问题大小增加一个乘法量（即将其大小乘以10），则做功仅增加一个加法量。
将此应用于二叉树问题，这样您就有了一个很好的应用程序：如果将二叉树中的节点数加倍，则高度仅增加1（一个加法量）。如果再增加一倍，它仍然只增加了1。（显然，我假设它保持平衡）。这样，当问题规模成倍增加时，你的工作量不会加倍，而只是做了稍微多一点的工作。这就是为什么O（logn）算法非常棒的原因。
下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。
二叉树是一种情况，其中大小为n的问题被划分为大小为n/2的子问题，直到我们达到大小为1的问题：
这就是你如何得到O（logn），这是在上面的树上需要完成的工作量，以获得解决方案。
具有O（logn）时间复杂度的常见算法是二进制搜索，其递归关系为T（n/2）+O（1），即在树的每个后续级别上，您将问题分成一半，并执行恒定数量的额外工作。
但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？
我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。
我无法理解如何用对数来识别函数时间
对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。
对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。
如果你正在寻找一个基于直觉的答案，我想为你提供两种解释。
想象一下一座很高的山，它的底部也很宽。要到达山顶，有两种方式：一种是一条围绕山顶螺旋延伸的专用通道，另一种是切割出的小露台状雕刻，以提供楼梯。现在，如果第一种方式在线性时间O（n）内到达，则第二种方式是O（logn）。想象一个算法，它接受整数n作为输入，并在时间上与n成比例地完成，那么它是O（n）或θ。
logx到基b=y是b^y=x的倒数
如果有深度为d、大小为n的M元树，则：
遍历整棵树~O（M^d）=O（n）在树中行走一条路径~O（d）=O（logn到基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（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。
你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。
我可以补充一些有趣的东西，很久以前我在科尔曼等的书中读过。现在，想象一个问题，我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。
现在，如果你能证明，在你的算法的每一次迭代中，你都切断了这个空间的一部分，这不小于某个极限，这意味着你的算法在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 that
for all N>N0 "C*g(n) > f(n) > 0" is true.
看来这个符号主要是从数学中提取出来的。
本文引用了一句话：D.E.Knuth，《大OMICRON、大OMEGA和大THETA》，1976年：
基于这里讨论的问题，我建议SIGACT以及计算机科学和数学期刊的编辑，采用上面定义的符号，除非有更好的替代方案很快就会发现。
今天是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 10
i: 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（n）与O（a^n）之间的区别（a是常数）。
分而治之范式中的算法具有复杂性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/
概述
其他人已经给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。因此，除了我的解释，我还将提供一些带有简单打印语句的算法，以说明不同算法类别的复杂性。
首先，你需要对对数有一个大致的了解，你可以从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的《数学家的喜悦》一书。
实际上，如果您有一个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）
首先，我建议您阅读以下书籍：；
算法（第4版）
下面是一些函数及其预期的复杂性。数字表示语句执行频率。
以下Big-O复杂性图表也取自bigocheatsheet
最后，非常简单的展示展示了它是如何计算的；
剖析程序的语句执行频率。
分析程序的运行时间（示例）。
每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数。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（logn）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
大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.
