为什么O(log2N) = O(log3N) ?
我不太理解这点。难道大O符号不意味着某个东西的上界吗?
log2N不比log3N 大吗?当我绘制它们的图形时,log2N在log3N上方。
Big O并不涉及常数因子,而Logx(n)和Logy(n)之间的区别只是一个常数因子。
换个说法,对数的底数基本上只修改了图表上线条/曲线的斜率。Big-O并不关心图表上曲线的斜率,只关心曲线的形状。如果你可以通过将其斜率向上或向下移动使一条曲线匹配另一条曲线,那么就在Big-O符号意义上它们是相同的函数和相同的曲线。
为了更好地理解,也许绘制一些常见曲线形状的图会有用:
如上所述,只有线的形状才重要,而不是它的斜率。在以下图中:
...所有线都是直线,因此即使它们的斜率差异激增,它们在大O符号意义上仍然相同--它们都只是O(N),无论斜率如何。对于对数来说,我们得到了大致相同的效果--每条线都会像前面图片中的O(log N)线一样弯曲,但是更改对数的底数将使该曲线绕原点旋转,因此你将(再次)获得相同的形状,但是斜率不同(因此,从大O符号意义上来看,它们都是相同的)。因此,回到最初的问题,如果我们更改对数的底数,我们将得到类似以下图表的曲线:
在这里,可能不太明显的是发生的只是斜率不断地变化,但这正是与上面的直线相同的区别。
这是因为更改对数的底数相当于将其乘以一个常数。而大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))
。
f(n)=3n
始终小于g(n)=1000n
,但它们都出现在O(n)
中,因为它们根据它们的表达式渐近地增长线性
。