algorithm - 寻找循环的复杂性

Question

我得到了这个算法，我被告知要找出它的复杂度 big theta。

for (i = 1; i <= n; i++) {
    j = n;
    while( j >= 1) {
        j = j/3;
    }

}

我知道外部 for 循环运行了 n 次。 while 循环虽然更棘手，但它可能是 log n(以 3 为底)。总共使它成为 n*log₃n

这是正确的吗？

Answer 1

有一个大小为 n 的外部 for 循环。它为总体复杂度贡献了一个 n 因子的复杂度。

假设内部 while 循环运行了 m 次。在第 i 次迭代之后，j 的值将为 n/(3^i)。我们将运行它直到 n/(3^i) > 1。因此，

=> n/(3^i) = m
=> n = 3^m
=> log(n) = log2(3) * m
=> m = O(log(n))

因此，for 循环的复杂度为 O(n)，而 while 循环的复杂度为 O(log(n))。嵌套循环的复杂度变为 O(n log(n))。