在此循环中找不到大时间 [英] Trouble Finding Big O Time for this loop

问题描述

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

I'm trying to find the Big O running time for the following code snippet:

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

由于n的乘积，我不确定是O(n ^ 3)还是O(n ^ 2).一些帮助，将不胜感激:)

I'm not sure if it would be O(n^3) because of the multiplication of n, or just O(n^2). Some help would be appreciated :)

推荐答案

内部循环将准确执行0 +1 + ... + n ^ 2-2 + n ^ 2-1-=(n ^ 2)(n ^ 2-1)/2次(请参见算术系列)，因此实际上是O(n ^ 4).

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).

这篇关于在此循环中找不到大时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！