O(log n) 到底是什么意思？
我正在学习 Big O Notation 运行时间和摊销时间。我理解 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，但我不明白如何识别具有对数时间的函数。
我无法理解如何识别具有日志时间的功能。
对数运行时间函数最常见的属性是：
选择执行某些操作的下一个元素是几种可能性之一，并且
只需要选择一个。
或者
执行动作的元素是 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(n2)：办公室发生错误，每个电话簿中的每个条目的电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。
O(n · n!)：我们已准备好将电话簿装载到装运码头上。不幸的是，本应装载书籍的机器人出现了故障：它正在以随机顺序将书籍放到卡车上！更糟糕的是，它会将所有书籍装载到卡车上，然后检查它们的顺序是否正确，如果不正确，它会卸载它们并重新开始。 （这是可怕的 bogo 排序。）
O(nn)：你修复了机器人，让它正确加载东西。第二天，您的一位同事对您进行恶作剧，并将装卸平台机器人连接到自动打印系统。每次机器人去加载原始电话簿时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统足够复杂，当遇到要加载的复制书时，机器人不会尝试打印更多的副本，但它仍然必须加载每本已打印的原始和复制书。
O(log N) 基本上意味着时间呈线性增长，而 n 呈指数增长。因此，如果计算 10 个元素需要 1 秒，则计算 100 个元素需要 2 秒，计算 1000 个元素需要 3 秒，依此类推。
当我们进行分而治之的算法（例如二分搜索）时，它是 O(log n)。另一个例子是快速排序，每次我们将数组分成两部分，每次需要 O(N) 时间来找到一个枢轴元素。因此它N O(log N)
log 可视化为图形上熟悉的对数曲线的人来说，这在精神上是一种负担。
这个问题已经发布了许多好的答案，但我相信我们确实错过了一个重要的答案——即图示的答案。
完全二叉树的高度为 O(log n) 是什么意思？
下图描绘了一个二叉树。请注意，每个级别包含的节点数量是上面级别的两倍（因此是二进制）：
https://i.stack.imgur.com/ZsiDW.png
二分搜索是一个复杂的例子 O(log n)。假设图 1 中树的底层节点表示某个排序集合中的项目。二分搜索是一种分而治之的算法，图中显示了我们将如何需要（最多）4 次比较来找到我们在这个 16 项数据集中搜索的记录。
假设我们有一个包含 32 个元素的数据集。继续上图，发现我们现在需要 5 次比较才能找到我们要搜索的内容，因为当我们乘以数据量时，树只增长了一层。因此，算法的复杂度可以描述为对数阶。
在一张普通纸上绘制 log(n)，将得到一个曲线图，其中曲线的上升随着 n 的增加而减速：
https://i.stack.imgur.com/qPNNp.png
概述
其他人给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。所以除了我的解释之外，我还会提供一些带有简单打印语句的算法来说明不同算法类别的复杂性。
首先，您需要对可以从 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(logn) 等视为增长的类别或类别。有些类别比其他类别需要更多时间。这些类别有助于为我们提供一种排序算法性能的方法。随着输入 n 的增长，一些增长得更快。下表以数字方式说明了所述增长。在下表中，将 log(n) 视为 log_2 的上限。
https://i.stack.imgur.com/4yiP0.jpg
各种大 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 循环轻松获得。
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";
概括
上面给出了几个直截了当的例子和变化，以帮助演示可以引入哪些细微的变化，而这些变化实际上不会改变分析。希望它能给你足够的洞察力。
O(n^2) 标记为 O(n) 和 O(n) 的组合会更好，所以 O(n) * O(n) = O(n * n) = O(n^2)。没有这个等式，感觉有点跳跃。这是对先前解释的重复，但我认为这种重复可以为读者提供更多理解的信心。
n 与 n/2 绘制成图表，您会发现它们都形成一条直线。这使它们处于同一类，因为它们具有相似的增长率（将其视为图表的形状）。同样，如果您将 log_2 与 log_3 绘制成图表，您会发现它们都具有“相似的形状”或“相似的增长率”。
n/2 or 2n or n+2 or n 在图中会有不同的线，但它们将具有相同的增长率，这意味着它们都将遵循线性增长。
下面的解释是使用完全平衡二叉树的情况来帮助您理解我们如何获得对数时间复杂度。
二叉树是这样一种情况，其中一个大小为 n 的问题被划分为大小为 n/2 的子问题，直到我们遇到大小为 1 的问题：
https://i.stack.imgur.com/spHFh.png
这就是您获得 O(log n) 的方式，这是需要在上述树上完成的工作量才能达到解决方案。
具有 O(log n) 时间复杂度的常见算法是二分搜索，其递归关系为 T(n/2) + O(1)，即在树的每个后续级别，您将问题分成两半并做恒定数量的额外工作。
log_2。您的观察将超出 log_2，并且对于 x > 1 中的任何 log_x 都是准确的。但是，直接除法可能不会导致 1，因此您可能想说递归除法，直到最新除法的 Ceiling() 等于 1，或类似的东西。
如果你有一个函数需要：
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) 时间。 Big O notation，松散地说，意味着该关系只需要对大 n 为真，并且可以忽略常数因子和较小的项。
log_2，它属于 O(log(n)) 类。在 O(log(n)) 的同一类中还有许多其他人，即 log_x 其中 x > 1
so O(log n) scales like 1 sec for 10 elements, 2 sec for 20, 3 for 40 etc 不准确。该模式/类将与 O(n) 而不是 O(log(n)) 匹配/对齐。如果有人对 log_10 感兴趣，则等效示例是 10 个元素 1 秒，100 个元素 2 秒，1000 个元素 3 秒，等等。
对数
好的，让我们尝试完全理解对数实际上是什么。
想象一下，我们有一根绳子，我们把它绑在一匹马上。如果绳子直接系在马身上，马需要拉开（例如，从男人身上）的力直接为 1。
现在想象绳子绕在一根杆子上。要逃跑的马现在必须用力拉很多倍。次数取决于绳子的粗糙度和杆子的大小，但我们假设它将一个人的力量乘以 10（当绳子转一圈时）。
现在，如果绳子绕了一次，马需要用力拉 10 倍。如果人类决定让马真的很困难，他可能会再次将绳子绕在一根杆子上，使其强度增加 10 倍。第三个循环将再次将强度增加 10 倍。
https://i.stack.imgur.com/wttFP.png
我们可以看到，对于每个循环，该值增加 10。获得任何数字所需的圈数称为该数字的对数，即我们需要 3 个帖子将您的力量乘以 1000 倍，6 个帖子将您的力量乘以1,000,000。
3 是 1,000 的对数，6 是 1,000,000（以 10 为底）的对数。
那么 O(log n) 实际上是什么意思呢？
在我们上面的例子中，我们的“增长率”是 O(log n)。每增加一个环，我们的绳索可以承受的力就会增加 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 为底）。
请注意，我将“最多”加粗。 Big-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)。
免责声明：绳索对数示例取自优秀的 Mathematician's Delight book by W.Sawyer。
In our example above, our 'growth rate' is O(log n). For every additional loop, the force our rope can handle is 10 times more，由显示 n== 循环数和 our 'growth rate' => 的图表支持。 10^n，这不是 log n。该示例可以通过使 n=# horses 更正，这需要 log n 循环来约束。糟糕的教学例子会培养出只相信自己理解的学生。
对数运行时间 (O(log n)) 本质上意味着运行时间与输入大小的对数成比例增长 - 例如，如果 10 个项目最多花费一些时间 x，并且 100 项最多需要 2x，10,000 项最多需要 4x，那么它看起来像 O(log n) 时间复杂度。
log 10,000 / log 100 都是 2。
首先，我建议您阅读以下书籍；
这是一些功能及其预期的复杂性。数字表示语句执行频率。
https://i.stack.imgur.com/inOnH.png
https://i.stack.imgur.com/jIGhf.png
最后一个非常简单的展示，展示了它是如何计算的；
程序语句执行频率的剖析。
分析程序的运行时间（示例）。
https://i.stack.imgur.com/Sz5Np.png
您可以通过说时间与 N 中的位数成正比来直观地想到 O(log N)。
如果一个操作对输入的每个数字或位执行恒定时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成正比，而不是输入的大小；因此，O(log N) 而不是 O(N)。
如果一个操作做出一系列恒定时间决策，每一个决策都将要考虑的输入大小减半（减少 3、4、5..），那么整个操作所花费的时间将与 log base 2（base 3 , base 4, base 5...) 的输入大小为 N，而不是 O(N)。
等等。
log<sub>10</sub> N 的解释，是吗？
什么是 logb(n)？
它是在达到大小为 1 的部分之前，您可以将长度为 n 的对数重复切割成 b 等份的次数。
我一直不得不在脑海中想象一个在 O(log n) 中运行的算法的最佳方法如下：
如果您将问题大小增加一个乘数（即，将其大小乘以 10），则工作只会增加一个相加量。
将此应用于您的二叉树问题，以便您有一个很好的应用程序：如果您将二叉树中的节点数加倍，则高度仅增加 1（添加量）。如果你再次加倍，它仍然只增加了 1。（显然我假设它保持平衡等等）。这样，当问题规模成倍增加时，您的工作量不会增加一倍，而您只需要做更多的工作。这就是 O(log n) 算法很棒的原因。
分而治之的算法通常对运行时间有一个 logn 组件。这来自输入的重复减半。
在二分搜索的情况下，每次迭代都会丢弃一半的输入。需要注意的是，在 Big-O 表示法中，log 是 log base 2。
编辑：如前所述，对数基数无关紧要，但是在推导算法的 Big-O 性能时，对数因子将来自减半，因此我将其视为基数 2。
O(log n) 有点误导，更准确地说是 O(log2 n)，即（以 2 为底的对数）。
平衡二叉树的高度为 O(log2 n)，因为每个节点都有两个（注意 log2 n 中的“二”）子节点。因此，具有 n 个节点的树的高度为 log2 n。
另一个例子是二分搜索，它的运行时间为 O(log2 n)，因为在每一步都将搜索空间除以 2。
但是 O(log n) 到底是什么？例如，>完全二叉树的高度为 O(log n) 是什么意思？
我将其改写为“完整二叉树的高度为 log 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)。
*请记住，大 O 符号 by definition 常量无关紧要。同样通过对数的change of base rule，不同基数的对数之间的唯一区别是一个常数因子。
这两种情况将花费 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);
}
它只是意味着此任务所需的时间随着 log(n) 的增长而增长（例如：n = 10 时需要 2 秒，n = 100 时需要 4 秒，...）。阅读有关 Binary Search Algorithm 和 Big O Notation 的 Wikipedia 文章以获得更精确的信息。
简而言之：在算法的每一步，您都可以将工作量减半。 （渐近等价于第三，第四，...）
如果您在图形计算器或类似工具上绘制对数函数，您会发现它的上升非常缓慢——甚至比线性函数还要慢。
这就是为什么具有对数时间复杂度的算法受到高度追捧的原因：即使对于非常大的 n（例如，假设 n = 10^8），它们的性能也超出了可接受的范围。
我可以添加一些有趣的东西，这是我很久以前在 Kormen 等人的书中读到的。现在，想象一个问题，我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。
现在，如果你能证明，在你的算法的每次迭代中，你都会切断这个空间的一小部分，这不小于某个限制，这意味着你的算法在 O(logN) 时间内运行。
我应该指出，我们在这里谈论的是相对分数限制，而不是绝对分数限制。二分搜索是一个经典的例子。在每一步，我们都会丢弃 1/2 的问题空间。但二分查找并不是唯一这样的例子。假设，你以某种方式证明，在每一步你至少丢掉 1/128 的问题空间。这意味着，您的程序仍然在 O(logN) 时间运行，尽管比二进制搜索慢得多。这是分析递归算法的一个很好的提示。通常可以证明，在每个步骤中，递归不会使用多个变体，这会导致问题空间中某些部分的截断。
实际上，如果您有一个包含 n 个元素的列表，并从该列表创建一棵二叉树（就像在分治算法中一样），您将继续除以 2，直到您到达大小为 1 的列表（叶子）。
在第一步，你除以 2。然后你有 2 个列表 (2^1)，你将每个列表除以 2，所以你有 4 个列表 (2^2)，你再除，你有 8 个列表 (2^3 ) 依此类推，直到您的列表大小为 1
这给了你等式：
n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps
（你取每一边的 lg，lg 是对数基数 2）
我可以举一个 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) 和 O(a^n) 之间的差异（a 是一个常数）。
每次我们编写算法或代码时，我们都会尝试分析其渐近复杂度。它不同于它的时间复杂度。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但是有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数，即。 1. 物理系统 2. 编程语言 3. 编码风格 4. 还有更多......
实际执行时间不是一个很好的分析度量。
相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。所以执行时间是输入大小的函数。
以下是线性时间算法的示例
线性搜索给定 n 个输入元素，要在数组中搜索一个元素，您最多需要进行 'n' 次比较。换句话说，无论你使用什么编程语言，喜欢什么编码风格，在什么系统上执行它。在最坏的情况下，它只需要 n 次比较。执行时间与输入大小成线性比例。
它不仅仅是搜索，无论工作（增量、比较或任何操作）是输入大小的函数。
因此，当您说任何算法都是 O(log n) 时，这意味着执行时间是 log 乘以输入大小 n。
随着输入大小的增加，完成的工作（这里是执行时间）增加。（因此成比例）
n Work
2 1 units of work
4 2 units of work
8 3 units of work
随着输入大小的增加，完成的工作也会增加，并且它独立于任何机器。如果你试图找出工作单位的价值它实际上取决于上面指定的参数。它会根据系统和所有的变化。
完整的二进制示例是 O(ln n)，因为搜索看起来像这样：
1 2 3 4 5 6 7 8 9 10 11 12
搜索 4 会产生 3 个命中：6、3 然后是 4。并且 log2 12 = 3，这很好地近似于需要多少命中。
https://i.stack.imgur.com/AwAho.png
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)
在信息技术中，它意味着：
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, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976：
基于这里讨论的问题，我建议 SIGACT 的成员以及计算机科学和数学期刊的编辑采用上述定义的符号，除非可以很快找到更好的替代方案。
今天是 2016 年，但我们今天仍在使用它。
在数学分析中，它意味着：
lim (f(n)/g(n))=Constant; where n goes to +infinity
但即使在数学分析中，有时这个符号也被用于表示“C*g(n) > f(n) > 0”。
据我在大学里知道，这个符号是由德国数学家朗道 (1877-1938) 引入的
O(logn) 是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二分搜索算法。
假设您必须在大小为 N 的数组中找到一个元素。
基本上，代码执行就像 NN/2 N/4 N/8....等
如果将每个级别完成的所有工作相加，您将得到 n(1+1/2+1/4....) 并且等于 O(logn)
log(n) 到底如何等于 n？！
如果您正在寻找基于直觉的答案，我想为您提供两种解释。
想象一个非常高的山丘，基础也非常宽阔。到达山顶有两种方式：一种是专门的小路，绕着山顶盘旋而上，另一种是：像雕刻一样的小露台切出一个楼梯。现在，如果第一种方法是在线性时间 O(n) 内达到，则第二种方法是 O(log n)。想象一个算法，它接受一个整数 n 作为输入并在与 n 成比例的时间内完成，那么它是 O(n) 或 theta(n) 但如果它的运行时间与数字的位数或位数成正比数字的二进制表示，然后算法在 O(log n) 或 theta(log n) 时间内运行。
分而治之范式中的算法的复杂度为 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/
关注公众号
不定期副业成功案例分享
N是一本书中的人数。因为电话簿中的每个人也都有自己的电话簿副本，所以有N个 相同 电话簿，每个电话簿中有N个人，即 O(N^2)。