计算算法的时间复杂度

Question

图片中为什么能作这样的替换

Answer 1

这个问题，用小学数学就能解释明白

logN 其实说白了，就是一个数字后面跟n个0

比如
log100=2
log1000=3

现在问你 100的3次方=1000的?次方，你肯定知道，100 x 100 x 100 = 1000 x 1000，所以是 2
为什么呢？小学数学告诉我们，2个零 x 3 = 3个零 x 2，这个叫做交换律。
用上面的log代替下，就是
100的(log1000)次方=1000的(log100)次方
也就是
a的logb次方=b的loga次方。

说白了，就是乘法的交换律放在指数上的推广。
一个数字如果是a个b的10次方相乘，那么也可以是b个a的10次方相乘。