math - 大O困惑:log2(N)vs log3(N)

Question

为什么O(log2N)= O(log3N)？

我不明白大O代表的不是上限吗？

log2N大于log3N吗？当我绘制它们时，log2N高于log3N。

Answer 1

Big O不处理常量因子，Logx(n)和Logy(n)之间的差是常量因子。

换句话说，对数的底线基本上只是修改图形上线/曲线的斜率。 Big-O与图形上曲线的斜率无关，而与曲线的形状有关。如果您可以通过向上或向下移动斜率来使一条曲线与另一条曲线匹配，那么就Big-O表示法而言，它们是相同的函数，并且是相同的曲线。

为了尝试对此进行透视，也许可以绘制一些更常见的曲线形状:

如上所述，虽然仅线条的形状重要，但其坡度并不重要。在下图中:



...所有直线都是直线，因此即使斜率根本不同，但就大O而言，它们仍然是相同的-无论斜率如何，它们都只是O(N)。使用对数，我们得到的效果大致相同-每条线将像上图中的O(log N)线一样弯曲，但是更改对数的底数将使该曲线绕原点旋转，因此(再次)具有相同的线形，但斜率不同(因此，就大O型而言，它们都是相同的)。因此，转到原始问题，如果我们更改对数的底数，我们将得到如下所示的曲线:



在这里，所发生的只是坡度的恒定变化可能不太明显，但这恰恰是这里的区别，就像上面的直线一样。