大O和嵌套循环

Question

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 <i被改为j <N*N,那么大O是否就是O(N ^ 3)呢？

Answer 1

从i = 1循环到n然后有一个从1到i的内部循环的函数将通过等于此公式的迭代次数:

n(n+1)/2

正如你所看到的,当我们摆脱除主指数之外的所有东西时,你以O(n ^ 2)结束

如果你从1循环到n然后有一个从1到n ^ 2的内部循环,那么是.你在O(n ^ 3),因为你经历的迭代次数将等于:

n^3

您在big O表示法中所关心的只是多项式中最大的元素,它描述了代码将经历的迭代次数.原因是因为随着n变大,除了最大元素之外的所有内容都很快无关紧要.当n很大时,我们只关心时间要求.因此,导致n ^ 3 + 5n ^ 2 + 2n次迭代的算法将具有O(n ^ 3)的大O符号.