runtime - 此伪代码的运行时

Question

谁能帮我分析以下伪代码的运行时间

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

我看到它的下限是 omega(n^3)，因为如果外部 for 循环内部只是 theta(1)，那就是它的样子。

我对仅在外循环的前 n 次迭代中运行的内循环感到困惑。我是否只是平均内部循环的运行时间：n^3 * ((1/n^2)*n + (1/n)*1，在这种情况下它是 O(n^3)？

score 2 · Accepted Answer

取决于你的编译器有多聪明。算法可以分为两部分（这可能有一个错误，但你明白了）

// i<n
// O(n^2)
for( i=0; i<n ; ++i )
  for( j=i; j<n; ++j )
    x++

// n < i < n*n*n
// O(n^3)
for( i=n ; i<n*n*n; ++j)
  noop(); //do nothing

第二部分什么i > n都不做，所以智能编译器只会将 i 循环到 n，在这种情况下它是 O(n^2)。

但是，如果您的编译器不智能，后半部分也会执行，您只会得到 O(1) 比较，因此整体行为是 O(n^3)。

score 1 · Accepted Answer

1

只有在i<n. 所以它是O(n^2)。

于 2011-11-03T01:44:54.923 回答

score 0 · Accepted Answer

你的算法应该像下面这样剖析：

for(i = 0; i < n*n*n; i++) {
    for(j = i; j < n; j++) {
        x++
    }
    if (i >= n) {
        y ++;
    }
}

wherex计算内循环和外循环的次数，并y在不再执行内循环时计算外循环的迭代次数。

因此，您可以像下面这样正式进行：

在此处输入图像描述

当时n = 10，结果为：x = 55，y = 990，与上面的公式兼容。

3 回答 3