算法的对数复杂度

Question

我很难理解算法的对数复杂性.

例如

for(int j=1; j<=n; j*=2){
    ...
}

其复杂程度为O(log ₂ N)

那怎么回事j*=3？复杂性将是O(log ₃ N)？

Answer 1

只要循环体是O(1),你就可以说是.

但是,请注意log ₃ N = log ₂ N/log ₂ 3,因此它也是O(log ₂ N),因为常数因子无关紧要.

还要注意,从这个论证可以看出,对于任何固定常数k,O(log _k N)也是O(log ₂ N),因为你可以3用k.