大O和嵌套循环 [英] Big O and Nested Loops

问题描述

void function(int N){
  for (int i=0; i<N; i++)
    for (int j= 0; j< i; j++)
      System.out.println("j")
}

对于此功能，Big O如何依赖第二个for循环，因为它是j

如果j<我被改成j< N * N，那么大O就是O(N ^ 3)吗?

For this function, how does the Big O depend on the second for loop because of it being j

Also, if j < i was changed to j< N*N, Would the big O just be O(N^3) then?

推荐答案

一个从i = 1循环到n，然后有一个从1循环到i的内部循环的函数将经过与该公式相等的迭代次数:

A function that loops from i = 1 to n and then has a inner loop that goes from 1 to i would go though a number of iteration equal to this formula:

n(n+1)/2

如您所见，当我们去除除主要指数以外的所有内容时，您将以O(n ^ 2)结尾

As you can see, when we get rid of everything besides the main exponent, you end with O(n^2)

如果从1循环到n，然后从1循环到n ^ 2，则可以.您处于O(n ^ 3)，因为您经历的迭代次数等于:

If you loop from 1 to n and then have an inside loop from 1 to n^2, then yes. You are at O(n^3) because the number of iteration you go through would be equal to:

n^3

您所关心的大O表示法是多项式中最大的元素，该元素描述了代码将经历的迭代次数.这样做的原因是，随着n变大，除最大元素外的所有其他元素都不会很快.而且，我们仅在乎n很大时的时间要求.因此，导致n ^ 3 + 5n ^ 2 + 2n次迭代的算法的O表示法将是O(n ^ 3).

All you care about in big O notation is the largest element in the polynomial that describes the number of iterations the code will go through. The reason for this is because everything besides the largest element quickly doesn't matter as n gets larger. And we only really care about the time requirements when n is large. So an algorithm that leads to n^3 + 5n^2 + 2n iterations would have a big O notation of O(n^3).

这篇关于大O和嵌套循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！