time-complexity - 将 P=2^(logN) 重写为 log2(P) = log2(N) 的解释是什么？

问题描述

我正在阅读《破解编码面试》的 Big-O 章节，无法理解建议的对数操作之一。

本书的第 50 页试图表明.O(2^{log N})O(N)

这本书以开头，然后声称：“根据 log ₂的定义，我们可以将其写为 log ₂ P = log ₂ N”Let P = 2^{log N}

这种说法是我的理解崩溃的地方。我不明白你怎么能减少到. 如果您查看这两个函数的图表，它们显然是不同的：log₂(2^{log N})log₂(N)

这是“证明”这一点的一步——这似乎也是一个错误的陈述。如果再次绘制它们，则为线性函数，而为次线性函数。N = 2^{log N}N2^{log N}

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

编辑以显示log N在这种情况下意味着 log-base-2(N)：

在书中的这个例子中，log N表示平衡二叉搜索树的近似深度。仅计算树的前几层就清楚地表明我们正在使用 log-base-2：

哪个日志函数给了我们答案“鉴于
节点，深度是多少？”显然答案是 log-base-2。

  节点深度 log2（节点） log10（节点）
      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。这本书增加了这种混乱，因为示例的部分引用了一个显式的，而描述树的深度的总是用假设的基数 2 编写的。log₂log N

标签： time-complexitybig-ologarithm

这是因为对数函数是指数函数的逆函数，即它们相互“撤销”。您可以将对数函数视为以下内容：“我必须将一个数字提高到什么幂才能得到另一个数字？当您考虑它时，假设相同的基数，听起来很像指数函数。对于例子，

$2^x=16$ 逻辑上等价于： $log16=x$ ，其中log 函数的基数是 2。

因此，使用此知识将 log 函数作为指数函数的指数会导致取消。它以某种方式“撤消”了指数。反之亦然，也会产生同样的结果。（即指数函数的对数，同底）

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

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

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

希望这会有所帮助！

time-complexity - 将 P=2^(logN) 重写为 log2(P) = log2(N) 的解释是什么？

问题描述

解决方案

推荐阅读