什么会导致算法具有O（log n）复杂性？
我对big-O的认识是有限的，当日志词汇出现在这个等式中时，它会让我失望得更多。
有人可以简单地向我解释一下O(log n)算法是什么？ 对数从哪里来？
当我试图解决这个中期实践问题时，这具体出现了：
令X（1..n）和Y（1..n）包含两个整数列表，每个列表都按非递减顺序排序。 给出一个O（log n）时间算法来查找所有2n组合元素的中值（或第n个最小整数）。 例如，X =（4,5,7,8,9）和Y =（3,5,8,9,10），则7是组合列表的中位数（3,4,5,5,7 ，8,8,9,9,10）。 [提示：使用二进制搜索的概念]
我不得不同意，第一次看到O（log n）算法时......这真的很奇怪......究竟哪里对数来自哪里？ 然而，事实证明，有几种不同的方式可以让您获得一个日志词，以大O标记显示。 这里有几个：
重复除以常数
取任意数字n; 比如说，16.在你得到一个小于或等于1的数字之前，你可以用n除以2来表示n次？ 16岁，我们有
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
请注意，这最终要完成四个步骤。 有趣的是，我们也有log2 16 = 4.嗯... 128怎么样？
128 / 2 = 64
64 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
这需要七个步骤，而log2 128 = 7。这是巧合吗？ 不！ 这有一个很好的理由。 假设我们将数n除以2 i次。 然后我们得到数字n / 2i。 如果我们想要解决这个值至多为1的i的值，我们可以得到
n / 2i≤1
n≤2i
log2 n≤i
换句话说，如果我们选择一个整数i使得i≥log2 n，那么在将n分成两半i后，我们将得到一个至多为1的值。保证这个值的最小i大致为log2 n，所以如果我们有一个算法除以2直到数量变得足够小，那么我们可以说它终止于O（log n）步骤。
一个重要的细节是，无论你将n分成什么常数（只要它大于1） 如果除以常量k，它将采用logn步骤来达到1.因此，任何将输入大小重复除以某个分数的算法都需要O（log n）次迭代来终止。 这些迭代可能需要很长时间，因此，净运行时不必是O（log n），但步数将为对数。
那么这个出现在哪里？ 一个典型的例子是二分法搜索，它是一种用于在有序数组中搜索值的快速算法。 算法的工作原理是这样的：
例如，在数组中搜索5
1 3 5 7 9 11 13
我们先看看中间元素：
1 3 5 7 9 11 13
^
由于7> 5，并且由于数组已被排序，所以我们知道数字5不能位于数组的后半部分，所以我们可以放弃它。 这离开了
1 3 5
所以现在我们看一下这里的中间元素：
1 3 5
^
由于3 <5，我们知道5不能出现在阵列的前半部分，所以我们可以抛出前半阵列离开
5
我们再次看看这个数组的中间部分：
5
^
由于这正是我们正在寻找的数字，我们可以报告5确实在数组中。
那么这个效率如何？ 那么，在每次迭代中，我们都抛弃至少一半剩余的数组元素。 只要数组为空或者我们找到了我们想要的值，算法就会停止。 在最坏的情况下，元素不在那里，所以我们保持数组的大小减半，直到元素用完。 这需要多长时间？ 那么，因为我们一直在反复切割数组，所以我们最多可以进行O（log n）次迭代，因为在我们运行之前我们不能将数组的数目削减一半以上（O（log n）次）超出数组元素。
遵循分而治之的一般技术（将问题分解成碎片，解决这些碎片，然后将问题重新组合在一起）的算法往往会出于同样的原因而存在对数项 - 您无法继续切割一些对象比O（log n）次多一半。 您可能希望将合并排序看作是一个很好的例子。
一次处理一个数字的值
基数为10的数字有多少个数字？ 那么，如果数字中有k位数字，那么我们就会知道最大的数字是10k的几倍。 最大的k位数是999 ... 9，k次，这等于10k + 1 - 1。因此，如果我们知道n有k个数字，那么我们知道n的值是大多数10k + 1 - 1。如果我们想用n来解决k，我们就可以得到
n≤10k+ 1 - 1
n +1≤10k+ 1
log10（n + 1）≤k+ 1
（log 10（n + 1）） - 1≤k
从中我们得到k近似为n的10的对数。 换句话说，n中的位数是O（log n）。
例如，让我们考虑添加两个太大而不适合机器字的大数字的复杂性。 假设我们有以10为底数表示的数字，我们将调用数字m和n。 增加他们的一种方法是通过小学方法 - 每次将数字写出一位数字，然后从右侧开始工作。 例如，要添加1337和2065，我们首先将数字编写为
1 3 3 7
+ 2 0 6 5
==============
我们添加最后一位数字并携带1：
1
1 3 3 7
+ 2 0 6 5
==============
2
然后，我们添加倒数第二个（“倒数第二”）数字并携带1：
1 1
1 3 3 7
+ 2 0 6 5
==============
0 2
接下来，我们添加倒数第三位（“antepenultimate”）数字：
1 1
1 3 3 7
+ 2 0 6 5
==============
4 0 2
最后，我们添加倒数第四（“preantepenultimate”...我爱英文）digit：
1 1
1 3 3 7
+ 2 0 6 5
==============
3 4 0 2
现在，我们做了多少工作？ 我们每个数字总共做O（1）个工作（即一个恒定的工作量），并且有O（max {log n，log m}）需要处理的总位数。 由于我们需要访问这两个数字中的每个数字，因此总共有O（max {log n，log m}）复杂度。
许多算法在某些基础中每次只能处理一位数字，从而得到一个O（log n）项。 一个典型的例子是基数排序，它一次排序整数一位数。 有许多基数排序的类型，但它们通常运行时间O（n日志U），其中U是正在排序的最大可能整数。 原因是每一次通过都需要O（n）次，并且总共需要处理O（log U）迭代来处理被排序的最大数字的每个O（log U）数字。 许多先进的算法，如Gabow的最短路径算法或福特 - 福克森最大流算法的缩放版本，其复杂度都有一个对数项，因为它们一次只能处理一位数字。
关于你如何解决这个问题的第二个问题，你可能想看看这个相关的问题，它探索了一个更高级的应用程序。 考虑到这里描述的问题的一般结构，当你知道结果中有一个记录项时，你现在可以更好地理解如何考虑问题，所以我建议不要在给出答案之前查看答案一些想法。
希望这可以帮助！
当我们谈论大哦的描述时，我们通常会谈论解决给定大小问题所需的时间。 通常，对于简单的问题，这个大小只是以输入元素的数量为特征，通常称为n或N.（显然，情况并非总是如此 - 图形的问题通常以顶点数V和边数E，但现在我们将讨论对象列表，列表中有N个对象。）
我们说一个问题“很大 - （N的一些函数）”当且仅当：
对于所有N>一些任意的N_0，存在一些常数c，使得算法的运行时间小于恒定的c次（某些N的函数）
换句话说，不要考虑设置问题的“固定开销”很重要的小问题，想想大问题。 而当考虑到大问题时，大的（一些N的函数）意味着运行时间总是少于某些常数时间的功能。 总是。
简言之，该函数是一个上限，达到一个常数因子。
所以，“log（n）的大 - 哦”意思是与上面所说的相同的东西，除了“用一些函数N”替换为“log（n）”。
所以，你的问题告诉你思考二进制搜索，所以我们来考虑一下。 假设您有一个按升序排序的N个元素列表。 你想知道某个给定的号码是否存在于该列表中。 一种不是二进制搜索的方法是只扫描列表中的每个元素，看看它是否是你的目标号码。 你可能会很幸运，并在第一次尝试中找到它。 但在最坏的情况下，你会检查N个不同的时间。 这不是二进制搜索，它不是很大 - 噢log（N），因为没有办法迫使它成为我们上面所描述的标准。
你可以选择这个任意常量为c = 10，如果你的列表中有N = 32个元素，那么你很好：10 * log（32）= 50，这大于32的运行时间。但是如果N = 64 ，10 * log（64）= 60，这小于64的运行时间。你可以选择c = 100或1000或者gazillion，你仍然可以找到一些N违反了这个要求。 换句话说，没有N_0。
如果我们进行二分搜索，我们会选择中间元素并进行比较。 然后我们丢掉一半的数字，再次重复，等等。 如果你的N = 32，你只能做5次左右，即log（32）。 如果你的N = 64，那么你只能做大约6次，等等。现在你可以选择这个任意的常数c，以这样的方式满足N的大值的要求。
在所有这些背景下，O（log（N））通常意味着你可以通过某种方式做一件简单的事情，将问题的大小减半。 就像二进制搜索在上面做的一样。 一旦你将问题减半，你就可以再次将它减半。 但是，关键的是，你不能做的是一些预处理步骤，这个步骤需要比O（log（N））时间更长的时间。 因此，例如，除非您可以在O（log（N））时间内找到一种方法，否则无法将两个列表整理为一个大列表。
（注意：几乎总是，Log（N）表示log-base-two，这正是我上面所假设的。）
在下面的解决方案中，所有具有递归调用的行在X和Y的子数组的一半给定大小上完成。其他行在一个固定的时间内完成。 递归函数是T（2n）= T（2n / 2）+ c = T（n）+ c = 0（lg（2n））= O（lgn）。
你从MEDIAN开始（X，1，n，Y，1，n）。
MEDIAN(X, p, r, Y, i, k)
if X[r]<Y[i]
return X[r]
if Y[k]<X[p]
return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
if X[q+1]>Y[j] and Y[j+1]>X[q]
if X[q]>Y[j]
return X[q]
else
return Y[j]
if X[q+1]<Y[j-1]
return MEDIAN(X, q+1, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j+1, k)
else
if X[q]>Y[j] and Y[j+1]>X[q-1]
return Y[j]
if Y[j]>X[q] and X[q+1]>Y[j-1]
return X[q]
if X[q+1]<Y[j-1]
return MEDIAN(X, q, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j, k)
上一篇: What would cause an algorithm to have O(log n) complexity?