如何计算嵌套 "for" 循环的 运行 时间？
How is the running time calculated for nested "for" loops?
最近开始使用这个所以需要你的帮助，假设你有如下所示的嵌套 for 循环，都从 1 到 n，如何计算相同的 运行 时间O, Theta, Omega?
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
在这种情况下，它们都是一样的，因为没有逻辑：
- 第一次循环：
1..N，N次迭代，O(N)（其他两个相同）
- 第二个循环：相同，
1..N，O(N)
所以，O(N*N) => O(N^2)。
关于theta one，我不习惯使用它，所以也许有人可以扩展答案。不过我觉得一样
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
那么让我们仔细看看这段代码。假设我们有一组 10 个项目 (n)，我们一个一个地执行这些循环。首先它必须通过 i 循环。他将它传递给 1，然后 1 进入第二个循环 10 次，然后 1 变成 2。总共它必须通过循环 100 次才能到达终点。在大 O 表示法中，我们总是针对最坏的情况计算 O。也就是说，需要一个位于循环末尾的项目。假设我们将 1 添加到 n。现在必须通过多少次循环？ 11 * 11 也就是 121。因此，每当您的输入增长 1 时，该算法的成本就会呈指数增长。这就是为什么我们说 O(n^2).
最近开始使用这个所以需要你的帮助，假设你有如下所示的嵌套 for 循环，都从 1 到 n，如何计算相同的 运行 时间O, Theta, Omega?
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
在这种情况下，它们都是一样的，因为没有逻辑：
- 第一次循环：
1..N，N次迭代，O(N)（其他两个相同） - 第二个循环：相同，
1..N，O(N)
所以，O(N*N) => O(N^2)。
关于theta one，我不习惯使用它，所以也许有人可以扩展答案。不过我觉得一样
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
那么让我们仔细看看这段代码。假设我们有一组 10 个项目 (n)，我们一个一个地执行这些循环。首先它必须通过 i 循环。他将它传递给 1，然后 1 进入第二个循环 10 次，然后 1 变成 2。总共它必须通过循环 100 次才能到达终点。在大 O 表示法中，我们总是针对最坏的情况计算 O。也就是说，需要一个位于循环末尾的项目。假设我们将 1 添加到 n。现在必须通过多少次循环？ 11 * 11 也就是 121。因此，每当您的输入增长 1 时，该算法的成本就会呈指数增长。这就是为什么我们说 O(n^2).