我对大 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。你可以将n除以2多少次，直到得到一个小于或等于1的数字？对于16，我们有
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
128 / 2 = 64
64 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
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)次。
遵循divide-and-conquer（将问题分成若干部分、解决这些部分，然后将问题重新组合）的通用技术的算法出于同样的原因，往往具有对数项 - 你不能将某个对象切成超过O(log n)次。您可能想看看merge sort，它是一个很好的例子。
一个十进制数n有多少个数字呢？如果这个数有k个数字，那么最大的数字是10的k次幂的某个倍数。最大的k位数是999...9，有k个9，等于10的k+1次幂减1。因此，如果我们知道n有k个数字，那么我们知道n的值最多为10的k+1次幂减1。如果我们想要解出k关于n的式子，我们得到：
n ≤ 10k+1 - 1
n + 1 ≤ 10k+1
log10 (n + 1) ≤ k + 1
(log10 (n + 1)) - 1 ≤ k
由此我们得出k大约是n的以10为底的对数。换句话说，n的位数是O(log n)。
例如，让我们考虑添加两个太大而无法适应机器字的大数字的复杂性。假设我们用十进制表示这些数字，并将这些数字称为m和n。一种加法方法是使用小学方法-逐位书写数字，然后从右到左进行计算。例如，要添加1337和2065，我们将首先将数字写出来。 1 3 3 7
+ 2 0 6 5
==============
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
1 1
1 3 3 7
+ 2 0 6 5
==============
3 4 0 2
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)
假设有数字X = 245436。这种“245436”的表示法中含有隐含信息。将该信息显式化:
X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0
这是该数字的十进制展开式。因此，表示该数字所需的最少信息为6位数字。这不是巧合，因为任何小于10^d的数字都可以用d位数字表示。
那么需要多少位数字来表示X？等于X中10的最大指数加1。
==> 10 ^ d > X
==> log (10 ^ d) > log(X)
==> d* log(10) > log(X)
==> d > log(X) // 并且log再次出现...
==> d = floor(log(x)) + 1
还要注意，这是表示此范围内数字最简洁的方式。任何缩减都会导致信息丢失，因为缺少的数字可以映射到其他10个数字。例如：12 * 可以映射到120、121、122、……、129。
取N = 10^d，我们使用最重要的观察结果：
这意味着，当要求在从0到N-1的整数线上搜索数字时，我们需要至少log(N)次尝试才能找到它。为什么？任何搜索算法都需要在搜索数字时逐个选择数字。唯一标识0到N-1之间的值所需的最小信息量= log(N)位数。
暂时无法评论...这是个死灵法师！ Avi Cohen的回答是不正确的，请尝试：
X = 1 3 4 5 8
Y = 2 5 6 7 9
没有任何一个条件为真，因此MEDIAN(X, p, q, Y, j, k)将切断两个5。这些是非递减序列，不是所有的值都是不同的。
还可以尝试具有不同值的偶数长度示例：
X = 1 3 4 7
Y = 2 5 6 8
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)
}
O(log n)可以理解为：如果您将问题规模n增加一倍，您的算法只需要增加常数步骤即可。 - phimuemue