将 P=2^(logN) 重写为 log2(P) = log2(N) 的解释是什么?

What is the explanation of rewriting P=2^(logN) as log2(P) = log2(N)?

我正在学习破解编码面试的 Big-O 章节,无法理解建议的对数运算之一。

本书第 50 页试图证明 O(2<sup>log N</sup>) 等价于 O(N)

这本书以 Let P = 2<sup>log N</sup> 开始,然后它提出:"By the definition of log2, we can write this as log2P = log2N"

这种说法是我理解失败的地方。我不明白如何将 log<sub>2</sub>(2<sup>log N</sup>) 减少到 log<sub>2</sub>(N)。如果你看一下这两个函数的图表,它们明显不同:

这是 'proving' 中的一个步骤,即 N = 2<sup>log N</sup> - 这似乎也是一个错误的陈述.如果您再次绘制它们,N 是一个线性函数,而 2<sup>log N</sup> 是一个次线性函数。

有任何对初学者友好的解释说明这是怎么回事吗?谢谢!


编辑以显示 log N 在这种情况下表示 log-base-2(N):

在书中的这个例子中,log N表示平衡二叉搜索树的近似深度。只需计算树的前几层就可以清楚地知道我们正在使用 log-base-2:

Which log function gives us the answer "Given the number of 
nodes, what is the depth?" Clearly the answer is log-base-2.

  nodes   depth   log2(nodes)   log10(nodes)
      1       1   0             0             
      3       2   1.58          0.48          
      7       3   2.81          0.85          
     15       4   3.91          1.18          
     31       5   4.95          1.49          
     63       6   5.98          1.80          

@陈凯文的回答很到位。我们在这里的 CS 世界中,假设的对数基数是 2。这本书增加了这种混淆,因为示例的某些部分引用了显式的 log<sub>2</sub> 而用于描述树的深度的 log N 总是以假定的基数 2 编写。

在 CS 中,很多 log() 函数都假定以 2 为底,所以 2^(logx) = x。您的绘图可视化假设以 10 为底。

这是软件工程专业学生经常遇到的问题。所有数学课程均采用基数 e,所有 CS 课程均采用基数 2,所有工程课程均采用基数 10。

这是因为对数函数是指数函数的反函数,即它们"undo"彼此。您可以将对数函数视为以下形式:“为了得到另一个数字,我必须提高多少次幂才能得到另一个数字?当您考虑时,假设基数相同, 听起来很像指数函数。例如,

在逻辑上等同于,其中对数函数的 base 是 2 .

因此,使用此知识计算对数函数作为指数函数的指数会导致取消。它以某种方式“撤销”指数。反之亦然,结果相同。 (即指数函数的对数,底数相同)

至于你的问题:为什么 O(2^logN) 等价于 O(N)?

这是因为,如上所述,指数函数正在提高相同基数的对数函数,这导致取消,只留下 N。因此,结果为O(N)

至于为什么你的图表看起来不对@Kaiwen Chen 对这个差异给出了很好的解释,涉及基数的差异。

希望对您有所帮助!