英文:
What will be the time complexity of a for loop nested 2 times?
问题
以下是已经翻译好的部分：
所以要估计时间复杂度的算法如下：
int a = 0;
for (i = 0; i < n; i++) // 从i遍历到n;
for (j = i; j < i * i; j++) // 从i遍历到i*i;
for (k = 0; k < j; k++) // 从0遍历到j;
a++;
我已经注释了我对该算法的基本理解。
外部循环显然运行了O(n)次，第一个内部循环从'i'到'i*i'运行。
第二个内部循环运行从'0'到'j'。
我也知道我必须应用乘法法则。
但是我无法计算两个内部循环相对于'n'的时间复杂度。
如果我对解释有误，请纠正我。
英文:
So the algorithm for which the time complexity is to estimated is this
int a = 0;
for (i = 0; i < n; i++) //runs from i-n;
for (j = i; j < i * i; j++) // runs from i - i*i;
for (k = 0; k < j; k++) //runs from 0 - j;
a++;
I have commented the basic details that i have understood about the algorithm.
The outer loop clearly runs O(n) times and first inner loop runs from 'i' to 'i*i'
The second inner loop runs '0' to 'j'
I also know i have to apply the rule of products.
But I am unable to calculate the time complexity of the two inner loops relative to 'n'.
Please correct me if I'm wrong with my explanation.
答案1
得分: 1
每当有疑虑时，始终使用数学，因为数学证明更容易理解，就像强大的直觉一样。
令 n 为输入的大小。
最内层循环，或者我们称之为第三个循环，运行了 j+1 次。
内部循环，或者第二个循环，运行了 i*i - i 次。
最后，外部循环运行了 n 次。
因此，整个程序的迭代次数可以用数学术语表示，如下图所示：
英文:
Whenever there is a doubt always use mathematics as the mathematical proofs are more palatable like strong intuitions.
Let n = size of input.
The innermost loop or lets call it as the 3rd loop runs for j+1 number of times.
The inner loop or 2nd loop runs for i*i - i number of times.
Finally, the outer loop for n times.
So, the number of iterations for the entire program can be expressed in mathematical terms as shown in the following figure:
答案2
得分: 0
当你有多层嵌套的循环时，请分别分析每个循环的复杂度，然后将它们相乘。
在这个示例中，第一个循环的复杂度是 O(n)，就像你所说的一样。
第二个循环的复杂度是 O(n^2)，因为在最坏的情况下，你需要执行的操作次数是 i*i 的数量级，可能达到 n^2。它并不在乎它不从零开始，因为在像 O(n^2 - n) 这样的表达式中，除了最高阶的项以外都会被忽略。
第三个循环同样需要 O(n^2)，因为在最坏的情况下，你可能需要执行与 j 一样多的操作，这也可能达到 n^2。
最后，a++ 发生在常数时间。将所有这些复杂度相乘，你得到一个复杂度为 O(n^5)。
英文:
When you have multiple levels of for loops, analyze the complexity of each loop in isolation and then multiply them together.
In this example, the complexity of the first loop is O(n), like you said.
The complexity of the second loop is O(n^2) because in the worst case, the number of operations you have to perform is on the order of i*i which could be as big as n^2. It doesn't matter that it doesn't start at zero either because in an expression like O(n^2 - n), everything but the highest order term gets ignored.
The third loop also takes O(n^2) because in the worst case, you could have as many as j operations would again could be as big as n^2.
Lastly a++ happens in constant time. Multiply everything together and you have a complexity of O(n^5).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论