英文:
Big O Time Complexity of Nested Loop with recursion
问题
下面是代码片段的时间复杂度计算：
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++) {
// 做了一些其他操作
}
}
关于复杂度计算的问题，你提出的 n^2(n + n^2) = O(n^4) 不正确。正确的时间复杂度是 O(n^n)，下面是详细解释：
doSomeOtherStuff函数的时间复杂度是 O(n)。doSomething函数内部包含了两层嵌套的循环，每一层的循环都是在 n 的基础上进行，所以可以认为有 n^n 个递归层级。- 在每个递归层级中，都会调用
doSomeOtherStuff函数，其时间复杂度是 O(n)。
因此，总的时间复杂度可以表示为 O(n^n)。这是因为在每个递归层级中，都会进行 O(n) 的操作，并且递归的层级数量随着 n 的增加呈指数级增长。
英文:
What should be the time complexity of below code snippet
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
}
}
Is the complexity calculation as: n^2(n + n^2) = O(n^4) is correct? If not please explain
答案1
得分: 2
根据我对第一个答案的评论，我认为这个算法的复杂性远远不止 O(n^4)。实际上，@ToddCaywood 首先写出了我脑中的想法。这个算法实际上类似于：
O(n^(n^2))
这是一个极其糟糕的结果。对于大型数据集，这个算法会飞出地球，永远不会回来。
我最初看待这个算法的方式是，每一层递归都会增加另一组嵌套的 for 循环。对于 n==10，你会有 20 个嵌套的 for 循环。随着 n 的增长，它会变得越来越深。
英文:
Per my comments to the first answer, I think the complexity of this algorithm is much worse than O(n^4). @ToddCaywood actually first wrote what I was thinking in my head. This algorithm is actually something like:
O(n^(n^2))
an impossibly bad result. For large datasets, this thing is going to go off into space and never come back.
The way I first looked at this is that each level of recursion adds another set of NESTED for loops. For n==10, you have 20 nested for loops. It just keeps getting deeper and deeper as n grows.
答案2
得分: 0
是的，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)。
如果你需要正式的证明，你可以相当容易地按照上面的逻辑进行，需要的地方进行展开。
英文:
Yes, O(n^4) is correct.
doSomeOtherStuff(n) is obviously complexity O(n), done n times, also done n times, so the inside portion is O(n^3).
Keeping this in mind, complexity of doSomething(n) [let's call that T(n)] = O(n^3) + T(n-1) where T(n-1) = O(n^3) + T(n-2), etc. Expanding to (n-1)(O(n^3)) + O(n^3) = n(O(n^3)) = O(n^4).
If you need a formal proof, you can follow the logic above pretty easily, expanded where needed.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论