重写P = 2 ^（logN）的解释是log2（P）= log2（N）？

Question

我正在研究Cracking the Coding Interview的Big-O章节，并且无法绕过建议的对数操作之一。

本书的第50页试图证明O(2log N)相当于O(N)。

本书从Let P = 2log N开始，然后它声称：“通过log2的定义，我们可以将其写为log2P = log2N”

这种说法是我理解失败的地方。我不明白你怎么能把log2(2log N)减少到log2(N)。如果你看一下这两个函数的图表，它们就明显不同了：

这是“证明”N = 2log N的一个步骤 - 这也似乎是一个错误的陈述。如果再次绘制它们，N是线性函数，而2log N是次线性函数。

这对于如何有意义的任何初学者友好的解释？谢谢！

---

编辑以显示在这种情况下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          

@Kaiwen Chen的回答是正确的。我们在这里处于CS的世界，假定的日志基数是2.这本书增加了这种混乱，因为示例的部分引用了明确的log2，而用于描述树深度的log N总是用假定的基数写成2。

Answer 1

在CS中，假设许多log（）函数是基数2，所以2 ^（logx）= x。您的绘图可视化假设基数为10。

这是软件工程专业学生处理的常见问题。所有数学课程都假定为基础e，所有CS课程都假定为2，所有工程课程都假定为10。

Answer 2

这是因为对数函数是指数函数的逆，即它们彼此“撤消”。您可以将对数函数视为以下内容：“为了得到另一个数字，我需要有多大的功率？当您考虑它时，假设相同的基数，听起来很像指数函数。例，

在逻辑上等效于：，其中log函数的基数为2。

因此，使用这种知识将日志函数作为指数函数的指数导致取消。它以一种“解除”指数的方式。相反的情况也是如此，并将产生相同的结果。 （即指数函数的对数，具有相同的基数）

至于你的问题：为什么O（2 ^ logN）等于O（N）？

这是因为，如上所述，指数函数正在提高相同基数的对数函数，这导致取消，仅留下N.因此，结果是O（N）

至于为什么你的图表看不见@Kaiwen Chen对这种差异做了很好的解释，涉及基数的差异。

希望这有帮助！