我目前正在学习Big O Notation运行时间和摊销时间。我理解的概念 上） 线性时间，意味着输入的大小成比例地影响算法的增长...例如，二次时间也是如此 上2） 等等。甚至算法，例如置换生成器，用 上！） 时代，通过阶乘增长。
例如，以下功能是 上） 因为算法与其输入成比例增长 ñ：
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
同样，如果有嵌套循环，则时间为O（n2）。
但到底是什么 O（log n）？例如，说完整二叉树的高度是什么意思 O（log n）？
我知道（也许不是非常详细）Logarithm是什么，在某种意义上：log10 100 = 2，但我无法理解如何识别具有对数时间的函数。
我无法理解如何识别具有日志时间的函数。
对数运行时函数最常见的属性是：
要么
这就是为什么，例如，在电话簿中查找人是O（log n）。你不需要检查 一切 在电话簿中找到合适的人;相反，您可以通过基于字母顺序查看其名称来简单地分而治之，并且在您最终找到某人的电话号码之前，您只需在每个部分中探索每个部分的子集。
当然，更大的电话簿仍然会花费更长的时间，但它不会像额外的大小成比例增长那么快。
我们可以扩展电话簿示例来比较其他类型的操作和 其 运行时间。我们假设我们的电话簿有 企业 （“黄页”），有独特的名称和 人 （“白页”），可能没有唯一的名称。电话号码最多分配给一个人或企业。我们还假设需要一段时间才能翻转到特定页面。
以下是我们可能在电话簿上执行的一些操作的运行时间，从最佳到最差：
O（1）（最佳情况）： 给定企业名称所在的页面和企业名称，找到电话号码。
O（1）（平均情况）： 给出一个人姓名所在的页面及其姓名，找到电话号码。
O（log n）： 给定一个人的姓名，通过在您尚未搜索的书的部分中间选择一个随机点来查找电话号码，然后检查该人的姓名是否在该点。然后在书名中那个人姓名所在的部分中间重复这个过程。 （这是对某个人姓名的二进制搜索。）
上）： 查找电话号码包含数字“5”的所有人。
上）： 给定电话号码，找到具有该号码的个人或企业。
O（n log n）： 打印机的办公室出现了混乱，我们的电话簿的所有页面都是以随机顺序插入的。通过查看每个页面上的第一个名称然后将该页面放在新的空白电话簿中的适当位置来修复排序以使其正确。
对于以下示例，我们现在在打印机的办公室。电话簿等待邮寄给每个居民或企业，每个电话簿上都有一个标签，标明应该邮寄到哪里。每个人或企业都有一本电话簿。
O（n log n）： 我们想要个性化电话簿，所以我们将在指定的副本中找到每个人或企业的名字，然后在书中圈出他们的名字，并为他们的赞助写一个简短的感谢信。
上2）： 办公室发生错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。取一些白色并删除每个零。
O（n·n！）： 我们准备将电话簿加载到运输码头。不幸的是，应该加载书籍的机器人已经变得混乱了：它正在以随机顺序将书籍放到卡车上！更糟糕的是，它将所有书籍加载到卡车上，然后检查它们是否按正确顺序排列，如果没有，则将其卸载并重新开始。 （这是可怕的 bogo sort。）
上ñ）： 您修复机器人，以便正确加载东西。第二天，你的一个同事对你进行恶作剧，并将装卸码头机器人连接到自动打印系统。每次机器人装载原始书籍时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统非常复杂，以至于当机器人遇到重复的书籍进行加载时，机器人不会尝试打印更多的副本，但它仍然需要加载已打印的每本原始和重复的书籍。
这个问题已经发布了许多好的答案，但我相信我们真的错过了一个重要的答案 - 即图解答案。
说完整二叉树的高度是O（log n）是什么意思？
下图描绘了二叉树。注意每个级别如何包含与上面的级别相比的节点数量的两倍（因此 二进制）：
二进制搜索是一个复杂的例子 O(log n)。假设图1中树底层中的节点表示某些已排序集合中的项目。二进制搜索是一种分而治之的算法，该图显示了我们将如何（最多）需要4次比较来查找我们在此16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的绘图，发现我们现在需要进行5次比较才能找到我们要搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，算法的复杂性可以描述为对数阶。
绘制 log(n) 在一张普通纸上，将产生一个图表，其中曲线的上升减速为 n 增加：
O(log N) 基本上意味着时间会线性上升 n 以指数方式上升。如果需要的话 1 第二个计算 10 元素，它将需要 2 计算秒数 100 元素， 3 计算秒数 1000 元素，等等。
是的 O(log n) 当我们划分和征服类型的算法，如二进制搜索。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要 O(N) 时间找到一个枢轴元素。因此 N O(log N)
下面的解释是使用完全的情况 均衡 二叉树，以帮助您了解我们如何获得对数时间复杂度。
二叉树是这样一种情况，其中大小为n的问题被分成大小为n / 2的子问题，直到我们遇到大小为1的问题：
这就是你得到O（log n）的方法，这是在上面的树上需要完成的工作量才能达到解决方案。
具有O（log n）时间复杂度的常见算法是二进制搜索，其递归关系是T（n / 2）+ O（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.
然后它需要日志2（n）时间。该 大O符号从松散的角度来说，这意味着只有大n的关系才需要，并且可以忽略常数因子和较小的项。
概观
其他人给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。因此，除了我的解释之外，我还将提供一些带有简单打印语句的算法来说明不同算法类别的复杂性。
首先，您需要了解Logarithm，您可以从中获得 https://en.wikipedia.org/wiki/Logarithm 。自然科学用途 e 和自然日志。工程学徒将使用log_10（log base 10），计算机科学家将使用log_2（log base 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的上限。
各种大O类别的简单代码示例：
O（1） - 常数时间示例：
算法1打印hello一次并且它不依赖于n，所以它总是在恒定时间内运行，所以它是 O(1)。
print "hello";
算法2打印hello 3次，但不依赖于输入大小。即使n增长，该算法也将始终只打印3次hello。那说3，是一个常数，所以这个算法也是 O(1)。
print "hello";
print "hello";
print "hello";
O（log（n）） - 对数例子：
算法3演示了一个在log_2（n）中运行的算法。注意for循环的post操作将i的当前值乘以2，所以 i 从1到2到4到8到16到32 ......
for(int i = 1; i <= n; i = i * 2)
print "hello";
算法4演示了log_3。注意 i 从1到3到9到27 ......
for(int i = 1; i <= n; i = i * 3)
print "hello";
算法5很重要，因为它有助于表明只要数字大于1并且结果重复地与自身相乘，那么您正在查看对数算法。
for(double i = 1; i < n; i = i * 1.02)
print "hello";
O（n） - 线性时间示例：
这个算法很简单，打印你好n次。
for(int i = 0; i < n; i++)
print "hello";
此算法显示一个变体，它将打印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）示例：
把它想象成一个组合 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类似于算法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平方示例：
O(n^2) 通过嵌套循环标准很容易获得。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
与算法10类似，但有一些变化。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O（n ^ 3） - n立方体示例：
这类似于算法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";
与算法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(log n)）本质上意味着运行时间与之成比例增长 对数 输入大小 - 例如，如果10个项目最多花费一些时间 x，最多100件物品，比方说， 2x，最多10,000件物品 4x那么它看起来像一个 O(log n) 时间复杂。
对数
好吧，让我们试着完全理解对数实际上是什么。
想象一下，我们有一根绳子，我们把它绑在一匹马上。如果绳子直接绑在马上，那么马需要拉开的力量（例如，从一个人身上拉开）直接是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 Force
0 | 1
1 | 10
2 | 100
3 | 1000
4 | 10000
n | 10^n
现在上面的例子确实使用了基数10，但幸运的是，当我们谈论大字符时，日志的基数是微不足道的。
现在让我们假设您正在尝试猜测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,10是1024的对数（基数2））。
请注意，我“最多”加粗。大写符号总是指更糟糕的情况。如果你很幸运，你可以在一次尝试中猜出这个数字，所以最好的情况是O（1），但这是另一个故事。
我们可以看到，每次猜测我们的数据集都在缩小。确定算法是否具有对数时间的一个好的经验法则是 在每次迭代后查看数据集是否按特定顺序缩小
那么O（n log n）呢？
你最终会遇到一个线性时间 O（n log（n） 算法。上面的经验法则再次适用，但这次对数函数必须运行n次，例如减少列表的大小 n次，它发生在像mergesort这样的算法中。
您可以轻松识别算法时间是否为n log n。寻找一个循环遍历列表的外循环（O（n））。然后看看是否有内环。如果内循环是 切割/减少 每次迭代的数据集，该循环是（O（log n），因此整个算法是= O（n log n）。
免责声明：绳索对数的例子是从优秀的抓取 由W.Sawyer撰写的数学家的喜剧书。