N上的嵌套for循环的复杂性和确切整数的复杂性？
N上的嵌套for循环的复杂性和确切整数的复杂性？
提问于 2017-10-29 14:30:13
我想知道，如果n和某个指定整数上的for循环都是循环的话，如何才能找到算法的大复杂度。例如，像这样的函数的复杂程度是什么：
for (int i=0; i < n; i++) {
for (int j=0; j < 100; j++) {
for (int k=0; k < n; k++) {
// Some O(1) operation here.
}
}
}现在，我知道外部循环和最内部的for循环都有复杂度O(n)，但是中间循环的复杂度是多少呢？O(100)，会否减至O(1)？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-10-29 14:47:29
是的，中间的是O(1)。这意味着，不管我输入的n是什么，它都不会运行100次。你不能再让它循环了。
但他们最外在和最内在的依赖于n。如果n是100，那么如果它是1000000，则最外层运行100次，那么是的，它运行1000000次。
最内环呢。对于最外层的每一次迭代，它运行100*n次。因此，总共它将运行100*n次。
现在想想他们做了多少工作？
100n^2+100n+n = An^2+B
O(n^2)将是时间复杂性。
O(10)或O(100)与O(100000)相同吗？
好的，我将避免编写更多的内容，因为任何常数C O(C)都等同于O(1)。
这里C是10或100或100000。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47001358
复制相关文章
相似问题
腾讯云开发者
