关于Big O表示法(N*N？)

Question

我有一些问题,我正试图找到大O. 令我困惑的是(N*N)问题:

for (i=1, sum=0, i <= N; i++) {
  for (j=1; j <= N*N; j++) {
     sum++;
  }
}

我猜它是O(N ^ 3),因为(N*N)可能代表两个循环.

for (i=1, sum=0, i <= N; i++) {
  for (j=1; j <= N*N; j++) {
     for (k=1; k<=j; k++) {
       sum++;
     }
  }
}

如果是这样,那么这个是O(N ^ 4)？

Answer 1

for (i=1, sum=0, i <= N; i++) {  // loop over i
  for (j=1; j <= N*N; j++) {     // loop over j, no dependency
     sum++;
  }
}

内循环j是独立的i并且具有复杂性O(N*N).外循环执行这N一次,因此O(N^3)总计.

for (i=1, sum=0, i <= N; i++) {  // loop over i
  for (j=1; j <= N*N; j++) {     // loop over j, no dependency
     for (k=1; k<=j; k++) {      // loop over k, dependent on j
       sum++;
     }
  }
}

循环k取决于j.j在整数上独立循环N*N.的总和1 + 2 + ... + N * N等于(N * N + 1) * N * N / 2其是O(N^4).再一次,循环i重复那个N时间,因此总复杂度是O(N^5).

为了计算大O,总是从最里面的循环开始并处理依赖关系!