algorithm - 双循环与运算次数的关系

Question

我的老师告诉我，基本上每当我们有一个循环和一个嵌套循环时，操作数如下 n(n+1)/2。

但是，我查看了一些程序，我意识到这不太可能。

for(i=0, i<n, n++)
 for(j=i, j<n, j++)
 {x=i+j}

在这种情况下，它将是 n(n+1)/2，忽略 i=0、j=0、n++、j++ 和 x=i+j，但这里：

for(i=0, i<n, n++)
 for(j=0, j<n, j++)
 {x=i+j}

除非我弄错了，否则它将是 n^n。

有人能准确告诉我两个循环何时有 n(n+1)/2 次操作吗？我现在有点困惑。

score 1 · Accepted Answer

在您的第一个示例中，该操作将进行n多次，然后是n-1多次，然后是n-2多次。如果我没记错的话，这是n(n-1)/2，但你可能是对的，它是n(n+1)/2。无论哪种方式，这是一个非常小的差异。

在你的第二个例子中，它会被完成n几次，然后是n次，然后n是次......直到你完成它n次n次 - 换句话说，n^2.

score 0 · Accepted Answer

您可能误解了老师（或老师犯了错误）。n(n-1)/2只是常见循环运行时的一个示例。它可以是你观察到的任何东西。您的第二个示例虽然有n^2操作，但这是另一种常见的模式。'n^n' 比较少见。

score 0 · Accepted Answer

for(i=0, i<n, n++)
 for(j=0, j<n, j++)
 {x=i+j}

第一个循环运行n时间，每次迭代你运行第二个循环n时间，因此你有n*n = n^2.

for(i=0, i<n, n++)
 for(j=i, j<n, j++)
 {x=i+j}

第一个循环运行n时间，每次迭代运行第二个循环(n-i)时间......因此x=i+j执行的次数是1 + 2 + 3 ..... + n次，这个序列是第一个n整数的总和，与 n(n+1)/2

3 回答 3