algorithm - 算法的对数复杂度

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。

Answer 2

基本上，是的。假设您的 for 循环如下所示：

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

a一些常量在哪里。如果for循环执行 k 次，那么在最后一次迭代中， j 将等于 a ^k。由于 N = O(j) 且 j = O( ^ak )，N = O( ^ak )。由此得出 k = O(log _a N)。再一次，for循环执行 k 次，因此该算法的时间复杂度为 O(k) = O(log _a N)。