algorithm - 递归，内循环和时间复杂度

考虑以下功能：

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）。有人能解释为什么吗？

最佳答案

递归调用几乎为复杂性提供了如下（表示输入的复杂性由T(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)。