是的，O(n^4(是正确的。
以下代码片段的时间复杂度应该是多少
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(是否正确？如果没有，请解释
根据我对第一个答案的评论，我认为这个算法的复杂性比O(n^4(差得多@事实上，ToddCaywood第一次把我的想法写在脑子里。这个算法实际上类似于：
O(n^(n^2))
糟糕得难以置信的结果。对于大型数据集，这种东西将进入太空，永远不会回来。
我第一次看到这一点的方式是，每一级递归都会添加另一组NESTEDfor循环。对于n==10，您有20个嵌套的For循环。它只是随着n的增长而越来越深。
doSometherstuff(n(显然是复杂性O(n(，做了n次，也做了n遍，所以内部是O(n^3(。
记住这一点，doSomething(n(的复杂性[让我们称之为T(n(]=O(n^3(+T(n-1(，其中T(n-1。
如果你需要一个正式的证明，你可以很容易地遵循上面的逻辑，并在需要的地方进行扩展。