嵌套循环的大O(int j = 0; j< i * i; ++ j) [英] Big O of Nested Loop (int j = 0; j < i * i; ++j)

问题描述

问题1

for (i = 0; i < n; i++) {
  for (j = 0; j < i * i ; j++){

  }
}
Answer: O(n^3)

乍看之下，O(n ^ 3)对我来说很有意义，但我记得我以前做过的一个问题:

At first glance, O(n^3) made sense to me, but I remember a previous problem I did:

问题2

for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(n)

对于问题2，外循环为O(log n)，内循环为O(2n/log n)，得出O(n).内部循环为O(2n/log n)，因为-参见此处的说明:

For Question 2, the outer loop is O(log n) and the inner loop is O(2n / log n) resulting in O(n). The inner loop is O(2n / log n) because - see explanation here: Big O of Nested Loop (int j = 0; j < i; j++)

为什么我们不像问题2那样做问题1，因为在问题1中，j也取决于i，这意味着我们实际上应该取内循环中将发生多少次迭代的平均值(因为我们做问题2).

Why we don't do Question 1 like Question 2 since in Question 1, j also depends on i which means we should really be taking the average of how many iterations will occur in the inner loop (as we do in Question 2).

我的答案是:外循环为O(n)，内循环为O(n ^ 2/n)，这导致问题1的O(n ^ 2).

My answer would be: O(n) for the outer loop and O(n^2 / n) for the inner loop which results in O(n^2) for Question 1.

推荐答案

您的答案是错误的.代码是Θ(n³).

Your answer is wrong. The code is Θ(n³).

请注意，内部循环最多执行i²个步骤，但最多执行n²个步骤，但对于一半外部循环，至少要执行(n/2)² = n²/4个

To see that note that the inner loop takes i² steps which is at most n² but for half of the outer loop iterations is at least (n/2)² = n²/4.

因此，内部总迭代次数最多为n * n² = n³，但至少为n/2 * n²/4 = n³/8.

Therefore the number of total inner iterations is at most n * n² = n³ but at least n/2 * n²/4 = n³/8.

您的考虑是错误的，因为内部循环平均与n²多次迭代成正比，而不是与n² / n一样.

Your consideration is wrong in that the inner loop takes on average proportional to n² many iterations, not n² / n.

这篇关于嵌套循环的大O(int j = 0; j&lt; i * i; ++ j)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！