递归、内循环和时间复杂度

Question

考虑以下函数：

int testFunc(int n){
    if(n < 3) return 0;
    int num = 7;
    for(int j = 1; j <= n; j *= 2) num++;
    for(int k = n; k > 1; k--) num++;
    return testFunc(n/3) + num;
}

我知道第一个循环是 O(logn)，而第二个循环是 O(n)，总时间复杂度是 O(n)。但是由于递归调用，我认为时间复杂度将是 O(nlogn)，但显然它只是 O(n)。谁能解释一下为什么？

Answer 1

对于使用如下递归算法的过程：

procedure T( n : size of problem ) defined as:
     if n < base_case then exit

     Do work of amount f(n) // In this case, the O(n) for loop

     T(n/b)
     T(n/b)
     ... a times... // In this case, b = 3, and a = 1
     T(n/b)
end procedure

应用 Master theorem 求时间复杂度，在这种情况下 f(n) 是 O(n) （由于第二个 for 循环，就像你说的）。这使得 c = 1.

现在，log_ba = log₃1 = 0，这就是第三种情况的定理，据此时间复杂度T(n) = Θ(f(n)) = Θ(n).

Answer 2

递归调用几乎给出了以下复杂度（用 T(n) 表示输入 n 的复杂度）：

T(n) = log(n) + n + T(n/3)

您正确注意到的第一个观察结果是您可以忽略对数，因为它由 n 控制。现在我们只剩下 T(n) = n + T(n/3)。例如，尝试将其写入 0。我们有：

T(n) = n + n/3 + n/9+....

你可以很容易地证明上面的和总是小于2*n。事实上，可以证明更好的限制，但这足以说明整体复杂度为 O(n).

递归、内循环和时间复杂度

Recursion, inner loop and time complexity

algorithm

recursion

time-complexity