big-o - 找不到此循环的大 O 时间

Question

我正在尝试查找以下代码片段的 Big O 运行时间：

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

我不确定它是否会因为 n 的乘法而为 O(n^3)，或者只是 O(n^2)。一些帮助将不胜感激:)

Answer 1

The inner loop will execute exactly 0 + 1 + ... + n^2 - 2 + n^2 - 1 = (n^2)(n^2 - 1)/2 times (see Arithmetic Series), so it's actually O(n^4).

Answer 2

for(i := 1 -> n ){
 for(j := 1 -> i ){
  东西
 }
}

运行在 O(n^2)[最内层循环运行 1,2,3....n 次，因为 n 的值增加，所以总共运行 1+2+3...+n = O(n^2)]

在您的示例代码中 let i := 1 -> p where p = O(n^2) 那么由于代码在 O(p^2) 中运行，因此其运行时间将为 O(n^4)

使用 Big-O 表示法可以帮助您度过某些情况。考虑一下：
for(i =n/2; i < n; i++){
 for(j = 2; j < n; j=j*2){
  something
 }
}

外循环运行O(n)，内循环运行O(log(n)) [将其视为不断将 n 除以 2：log 的定义]
，因此总运行时间为：O(n(logn))

Answer 3

找出算法迭代次数的精确而正式的方法：