带递归的嵌套循环的大 O 时间复杂度

Question

下面代码片段的时间复杂度应该是多少

void doSomething(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            doSomeOtherStuff(n);
            doSomething(n - 1);
        }
    }
}

void doSomeOtherStuff(int n) {
    for (int i = 0; i < n; i++) {
        //did some other stuff
    }
}

复杂度计算为：n^2(n + n^2) = O(n^4) 是否正确？如果不是请解释

Answer 1

是的，O(n^4) 是正确的。

doSomeOtherStuff(n)显然是复杂度O(n)，做了n次，也做了n次，所以里面的部分是O(n^3)。

记住这一点，doSomething(n) 的复杂性[让我们称之为 T(n)] = O(n^3) + T(n-1) 其中 T(n-1) = O(n ^3) + T(n-2) 等。扩展为 (n-1)(O(n^3)) + O(n^3) = n(O(n^3)) = O(n^ 4).

如果您需要正式证明，您可以很容易地遵循上面的逻辑，在需要的地方进行扩展。

Answer 2

根据我对第一个答案的评论，我认为这个算法的复杂度比 O(n^4) 差很多。 @ToddCaywood 实际上首先写下了我脑海中的想法。这个算法实际上是这样的：

O(n^(n^2))

一个不可能的坏结果。对于大型数据集，这个东西会进入 space 并且永远不会回来。

我首先看到的是递归的每一层都添加了另一组 NESTED for 循环。对于 n==10，您有 20 个嵌套的 for 循环。随着 n 的增长，它只会越来越深。

带递归的嵌套循环的大 O 时间复杂度

Big O Time Complexity of Nested Loop with recursion

java

time-complexity