如何将 O(2^(logN)) 简化为 O(N)

Question

在 Cracking the Coding Interview 中有一个示例，其中计算二叉搜索树中节点的递归算法的运行时间为 O(2^(logN))。这本书解释了我们如何简化得到 O(N) 这样...

2^p = Q 
logQ = P 
Let P = 2^(logN).

但是当他们说 Let P = 2^(logN) 时我迷路了。我不明白我们怎么知道如何将这两个设置为彼此相等，我也不明白下一步......（尽管他们告诉我他们通过对数基数 2 的定义来做到这一点）

logP = logN 
P = N 
2^(logN) = N

因此代码的运行时间为 O(N)

Answer 1

^{假设logN为log₂N}

这一行：

Let P = 2^(logN).

只是假设 P 等于 2^(logN)。您还不知道 N，您只是定义 P 和 N 之间的关系。

稍后，您可以对等式两边应用log函数。而由于 log(2^(logN)) 是 logN，下一步是：

logP = logN

而且，显然，当 logP = logN 时，则：

P = N

并且之前您假设 P = 2^(logN)，然后：

2^(logN) = N

此外，所有这些都可以通过 log 函数的定义简化为 2^logN = N。

Answer 2

对数的定义是“需要将底数提高多少次方才能得到这个值”所以如果对数的底数是 2，那么将 2 提高到那个次方就可以得到原始值。

示例：N 是 256。如果我们取它的以 2 为底的对数，我们得到 8。如果我们将 2 提高到 8 的次方，我们得到 256。所以它是线性的，我们可以使它只是 N .

如果对数的基数不同，例如10，则转换只需要将指数除以一个常数，使更准确的形式成为N = 2^(log N / log 2)，可以改为N / 2^(1 / log 2) = 2^log N。这里左边 N 的除数是一个常数，所以我们在讨论复杂性时可以忘记它，然后再次来到 N = 2^log N。

你也可以亲手测试一下。 256 的 Log2 为 8。128 的 Log2 为 7。8/7 约为 1.14。 256 的 Log10 是 2.4。 128 的 Log10 是 2.1。 2.4/2.1 约为 1.14。所以基数并不重要，你得到的值是不一样的，但它是线性的。所以在数学上 N 不等于 2^Log10 N，但在复杂性方面它确实如此。

Answer 3

简短的回答是，原始问题可能隐含地假设对数应该以 2 为底，因此根据 [= 的定义，2^(log_2(N)) 就是 N 57=](x) 作为 2^y 的反函数。

但是，如果对数是基于不同的底数，则更仔细地检查一下会很有趣。标准结果允许我们以 b 为底写对数，如下所示：

其中 ln(x) 是自然对数（使用基数 e）。类似地，可以重写 2^x 如下：

然后我们可以重写原来的order-expression如下：

可以简化为：

所以，如果我们的对数的底 b 是 2，那么这显然就是 N。但是，如果基数不同，那么我们会得到 N 的幂。例如，如果 b=10 我们得到 N 的 0.301 次方，这绝对是一个比 O(N).

更慢的递增函数

我们可以使用以下 Python 脚本直接检查：

import numpy
import matplotlib.pyplot as plt

N = numpy.arange(1, 100)

plt.figure()
plt.plot(N, 2**(numpy.log2(N)))
plt.xlabel('N')
plt.ylabel(r'^{\log_2 N}$')

plt.figure()
plt.plot(N, 2**(numpy.log10(N)))
plt.xlabel('N')
plt.ylabel(r'^{\log_{10} N}$')

plt.show()

当我们假设对数以二为底时生成的图形：

与取对数以十为底时的图形非常不同：

如何将 O(2^(logN)) 简化为 O(N)

How to simplify O(2^(logN)) to O(N)

runtime

time-complexity