algorithm - 这段代码的时间复杂度是多少？ (log3n)

Question

我有这段代码，我必须知道它的时间复杂度，我是这个主题的初学者，它让我有点困惑。

void func(int n){
   while(n > 0 && n % 3 ==0){
       do_computation(n);
       n = n/3;
   }
}

函数do_computatation的时间复杂度为1，那么func最坏的情况将是O(log3n) 是这样吗？

Answer 1

是的，它是 O(log₃n)，但这与 O(log n) 相同。基数并不重要，因为 log_an = (log_ab)(log_bn)，而常数因子则无关紧要事情。

编辑:

log(a^b) = b log(a)(任意基数)

n = b^log_bn
取两边的log_a:
log_an = log_a(b^log_bn)
=(log_bn)(log_ab)