将 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 对这个差异给出了很好的解释,涉及基数的差异。
希望对您有所帮助!
我正在学习破解编码面试的 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 对这个差异给出了很好的解释,涉及基数的差异。
希望对您有所帮助!