大O混淆:log2(N)vs log3(N)
Dav*_*far 18 math big-o logarithm
为什么O(log 2 N)= O(log 3 N)？
我不明白这一点.大O不是指某事的上限吗？
log 2 N 是否大于log 3 N？当我绘制它们时,log 2 N高于log 3 N.
Jer*_*fin 31
Big O不处理常数因子,Log x(n)和Log y(n)之间的差异是一个常数因子.
换句话说,对数的基数基本上只是修改图上线/曲线的斜率.Big-O不关心图上曲线的斜率,只关注曲线的形状.如果你可以通过向上或向下移动其斜率来获得一条曲线来匹配另一条曲线,那么就Big-O符号而言,它们是相同的函数和相同的曲线.
为了尝试透视这一点,也许绘制一些更常见的曲线形状会很有用:
如上所述,只有线的形状很重要,而不是它的斜率.在下图中:
......所有的线都是直的,所以尽管它们的斜率根本不同,但就大O来说它们仍然完全相同 - 它们都只是O(N),无论斜率如何.使用对数,我们得到大致相同的效果 - 每条线将像上一张图片中的O(log N)线一样弯曲,但是改变对数的底部将围绕原点旋转该曲线,因此您将(再次)他有相同的线条形状,但在不同的斜坡上(因此,就大O而言,它们都是相同的).所以,回到最初的问题,如果我们改变对数的基数,我们得到的曲线看起来像这样:
这里可能有点不太明显,所发生的一切都是斜率的不断变化,但这正是这里的差异,就像上面的直线一样.
- 我还要指出的是，转移并不重要，因为我们也忽略了常数的乘法。即使2n并非n的上移，f还是f（n）还是f = 2n都是O（n）。实际上，我想说的是，忽略常数因素是大O的一个更重要的特征。 (2认同)
luk*_*k32 14
这是因为改变对数的基数等于将其乘以常数.大O不关心常数.
log_a(b) = log_c(b) / log_c(a)
所以要从中log2(n)得到log3(n)你需要乘以它1 / log(3) 2.
换句话说log2(n) = log3(n) / log3(2).
log3(2)是一个常数O(cn) = O(n),因此O (log2(n)) = O (log3(n))
| 归档时间： |
|
| 查看次数： |
28984 次 |
| 最近记录： |