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 次操作吗？我现在有点困惑。

Answer 1

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

在您的第二个示例中，它将完成 n 次，然后是 n 次，然后是 n 次...直到您完成 n 次 n 次——换句话说，n^2。