什么会导致algorithm具有O（log n）的复杂性？
我对big-O的认识是有限的，当log方程出现在方程中的时候，它会把我抛到更远的地方。
有人可以简单地向我解释一下O(log n)algorithm是什么？ 对数从哪里来？
当我试图解决这个中期实践问题时，这是特别提出的：
让X（1..n）和Y（1..n）包含两个整数列表，每个列表按非递减顺序sorting。 给出一个O（log n）时间algorithm来查找所有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）。 [提示：使用二进制search的概念]
我不得不同意，第一次看到O（log n）algorithm，这个对数是从哪里来的？ 然而，事实certificate，有几种不同的方式可以让你获得一个logging词，以大O标记出现。 这里有几个：
重复地除以常数
采取任何数字n; 说，16.在你得到一个小于或等于1的数字之前，你可以用n除以2来分？ 16，我们有
16 / 2 = 8 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
注意，这最后要完成四个步骤。 有趣的是，我们也有这个log 2 16 = 4.嗯… 128呢？
128 / 2 = 64 64 / 2 = 32 32 / 2 = 16 16 / 2 = 8 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
这花了七个步骤，而日志2 128 = 7。这是巧合吗？ 不！ 这有一个很好的理由。 假设我们将n除以2 i次。 那我们得到n / 2的数字 如果我们想解决这个值至多为1的i的值，我们得到
n / 2 i≤1
n≤2 i
log 2 n≤i
换句话说，如果我们select一个整数i，使得i≥log2 n，那么在将n分成两半i后，我们将得到一个至多为1的值。保证这个最小的i大致是log 2所以如果我们有一个algorithm，除以2，直到数量变得足够小，那么我们可以说，它终止于O（log n）步骤。
一个重要的细节是，不pipe你用什么常数来划分（只要它大于一）。 如果除以常量k，则将需要log k n个步骤来达到1.因此，任何将input大小重复分割一小部分的algorithm都需要O（log n）次迭代来终止。 这些迭代可能需要很长时间，所以净运行时不需要是O（log n），但是步数是对数的。
那么这是从哪里来的？ 一个典型的例子就是二分查找 ，一种用于在一个sorting数组中search一个值的快速algorithm。 algorithm是这样工作的：
- 如果数组为空，则返回数组中不存在的元素。
- 除此以外：
- 看看数组的中间元素。
- 如果它等于我们正在寻找的元素，则返回成功。
- 如果它大于我们要找的元素：
- 扔掉arrays的后半部分。
- 重复
- 如果它小于我们正在寻找的元素：
- 扔掉arrays的前半部分。
- 重复
例如，要在数组中search5
1 3 5 7 9 11 13
我们先看看中间的元素：
1 3 5 7 9 11 13 ^
由于7> 5，并且由于数组已经sorting，所以我们知道数字5不能位于数组的后半部分，所以我们可以放弃它。 这离开了
1 3 5
所以现在我们看一下这里的中间元素：
1 3 5 ^
由于3 <5，我们知道5不能出现在arrays的前半部分，所以我们可以抛出前半arrays离开
5
我们再来看看这个数组的中间部分：
5 ^
由于这正是我们正在寻找的数字，我们可以报告5确实在数组中。
那么这个效率如何？ 那么，在每次迭代中，我们至less丢掉剩下的一半数组元素。 一旦数组为空或者我们find所需的值，algorithm就会停止。 在最坏的情况下，元素不在那里，所以我们保持数组的大小减半，直到元素用尽。 这需要多长时间？ 那么，因为我们不断地将数组重复一次又一次地重复，所以我们最多可以做O（log n）次迭代，因为在我们运行之前我们不能把数组的数目削减一半多于O（log n）次数组元素。
遵循分而治之的一般技术（将问题分解成碎片，解决这些碎片，然后将问题放回原处）的algorithm往往会出于同样的原因而存在对数项 – 您无法继续切割某个对象比O（log n）次多一半。 您可能想要看看合并sorting作为一个很好的例子。
一次处理一个数字的值
在基数为10的数字中有多less个数字？ 那么，如果这个数字有k个数字，那么我们就会知道最大的数字是10k的几倍。 最大的k位数是999 … 9，k次，这等于10 k + 1 – 1。因此，如果我们知道n有k个数字，那么我们知道n的值是最多10 k + 1 – 1。如果我们想用n来解决k，我们可以得到
n≤10 k + 1 – 1
n +1≤10k + 1
log 10 （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
接下来，我们添加倒数第三个（“倒数第二个”）数字：
1 1 1 3 3 7 + 2 0 6 5 ============== 4 0 2
最后，我们添加倒数第四（“preantepenultimate”…我爱英文）数字：
1 1 1 3 3 7 + 2 0 6 5 ============== 3 4 0 2
现在，我们做了多less工作？ 我们每个数字完成一个O（1）个工作（即一个恒定的工作量），并且有O（max {log n，log m}）个需要处理的总位数。 由于我们需要访问这两个数字中的每个数字，所以总共有O（max {log n，log m}）复杂度。
许多algorithm在某些基础上一次只能工作一个数字，从而得到一个O（log n）项。 一个典型的例子是基数sorting ，它一次sorting整数一个数字。 有许多基数sorting的types，但是它们通常运行时间为O（n日志U），其中U是正在sorting的最大可能整数。 其原因是每一次sorting都需要O（n）个时间，并且总共需要处理O（log U）迭代来处理被sorting的最大数字的每个O（log U）数字。 许多先进的algorithm，比如Gabow的最短pathalgorithm或者福特 – 福克森最大streamalgorithm的缩放版本，其复杂性都有一个对数项，因为它们一次只能处理一位数字。
关于你如何解决这个问题的第二个问题，你可能想看看这个相关的问题 ，探讨一个更高级的应用程序。 考虑到这里描述的问题的一般结构，当你知道结果中有一个logging项时，你现在可以更好地理解如何考虑问题，所以我build议不要在给出答案之前查看答案一些想法。
希望这可以帮助！
当我们谈论大哦描述的时候，我们通常会谈论解决给定大小的问题所需的时间 。 通常，对于简单的问题，这个大小只是以input元素的数量为特征，通常称为n或N.（显然，这并不总是正确的 – graphics的问题通常以顶点数V和边数E，但现在我们将讨论对象列表，列表中有N个对象。
我们说一个问题“是大的 – （N的一些函数）” 当且仅当 ：
对于所有N>一些任意的N_0，存在一些常数c，使得algorithm的运行时间小于常数c次（某些N的函数）
换句话说，不要去思考一个小问题，那就是设置问题的“不变的开销”，考虑一下大问题。 而当考虑到大的问题时，大的（一些N的函数）意味着运行时间总是less于某个常量的那个函数。 总是。
总之，这个函数是一个上限，达到一个常数因子。
所以，“log（n）的大哦”就是和上面说的一样的东西，除了用“log（n）”代替“N的某个函数”。
所以，你的问题告诉你思考二进制search，所以我们来考虑一下。 假设您有一个按升序sorting的N个元素的列表。 你想知道某个给定的号码是否存在于该列表中。 一种不是二进制search的方法是只扫描列表中的每个元素，看看它是否是你的目标号码。 你可能会很幸运，并在第一次尝试中find它。 但在最坏的情况下，你会检查N个不同的时间。 这不是二进制search，它不是大的 – 日志（N）的哦，因为没有办法强迫它成为我们上面所勾画的标准。
你可以select这个任意常量为c = 10，如果你的列表中有N = 32个元素，那么你很好：10 * log（32）= 50，这大于32的运行时间。但是如果N = 64 ，10 * log（64）= 60，小于64的运行时间。你可以selectc = 100，或者1000，或者gazillion，你仍然可以find一些违反这个要求的N。 换句话说，没有N_0。
如果我们进行二分search，我们select中间元素，并进行比较。 然后我们丢掉一半的数字，再做一遍，等等。 如果你的N = 32，你只能做5次左右，这就是log（32）。 如果你的N = 64，那么你只能这样做6次左右，等等。现在你可以select这个任意的常量c，这样一个总是满足N的大值的要求。
在所有这些背景下，O（log（N））通常意味着你有办法做一件简单的事情，将问题的大小减半。 就像上面的二进制search一样。 一旦你把这个问题减半了，你就可以把它再次削减一半。 但是，关键的是，你不能做的是一些预处理步骤，这个步骤需要比O（log（N））时间更长的时间。 因此，例如，除非在O（log（N））时间内find一种方法，否则不能将两个列表整理成一个大列表。
（注意：几乎总是，Log（N）表示log-base-two，这就是我上面所说的）。
在下面的解决scheme中，所有具有recursion调用的行都在给定大小的X和Y的子数组的一半的大小上完成。其他行在一个固定的时间内完成。 recursion函数是T（2n）= T（2n / 2）+ c = T（n）+ c = O（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)
还不能评论… necro是！ 阿维·科恩的答案是不正确的，请尝试：
X = 1 3 4 5 8 Y = 2 5 6 7 9
没有一个条件是真的，所以MEDIAN（X，p，q，Y，j，k）将会削减这五个。 这些是非降序，并不是所有的值都是不同的。
也可以尝试使用不同值的偶数长度示例：
X = 1 3 4 7 Y = 2 5 6 8
现在MEDIAN（X，p，q，Y，j + 1，k）将会削减四个。
相反，我提供这个algorithm，用MEDIAN（1，n，1，n）来调用它：
MEDIAN(startx, endx, starty, endy){ if (startx == endx) return min(X[startx], y[starty]) odd = (startx + endx) % 2 //0 if even, 1 if odd m = (startx+endx - odd)/2 n = (starty+endy - odd)/2 x = X[m] y = Y[n] if x == y //then there are n-2{+1} total elements smaller than or equal to both x and y //so this value is the nth smallest //we have found the median. return x if (x < y) //if we remove some numbers smaller then the median, //and remove the same amount of numbers bigger than the median, //the median will not change //we know the elements before x are smaller than the median, //and the elements after y are bigger than the median, //so we discard these and continue the search: return MEDIAN(m, endx, starty, n + 1 - odd) else (x > y) return MEDIAN(startx, m + 1 - odd, n, endy) }
当解决scheme基于n上的迭代时，我们称时间复杂度为O（log n），其中在每次迭代中完成的工作是先前迭代的一小部分，因为algorithm对解决scheme起作用。
