非正统嵌套 for 循环的时间复杂度
Time complexity of an unorthodox nested for loop
我已经阅读了一些处理时间复杂度和循环的帖子，并且对以下嵌套 for 循环的时间复杂度有疑问，以确保我的解决方案：
for(int i = 0; i < n; i++){
for(int j = n; j > i; j--){
#print something
}}
现在我知道外层循环的时间复杂度是O(n)，因为迭代次数是n。
然而，我想内部循环应该只迭代 n/2 次，因为当 i 向 n 递增时，j 以相同的方式从 n 向 0 递减。因此，内部循环应该在 n/2 次迭代后停止。
因此，我建议时间复杂度为 O(n*n/2) 或简化为 O(n^2)。
我对吗？提前致谢。
让我们看看循环是怎样的 运行ning:
- i=0 => j 将 运行 从 1 到 n => n 次
- i=1 => j 将 运行 从 2 到 n => (n-1) 次
- i=2 => j 将 运行 从 3 到 n => (n-2) 次
- .................................................
- i=n-1 => j 将 运行 从 n 到 n => 1 次
所以将所有项相加，我们得到
n + (n-1) + (n-2) + .... + 1 = n*(n+1)/2
这等于 O(n^2)。所以是的，你的结论是正确的。
我已经阅读了一些处理时间复杂度和循环的帖子，并且对以下嵌套 for 循环的时间复杂度有疑问，以确保我的解决方案：
for(int i = 0; i < n; i++){
for(int j = n; j > i; j--){
#print something
}}
现在我知道外层循环的时间复杂度是O(n)，因为迭代次数是n。 然而，我想内部循环应该只迭代 n/2 次，因为当 i 向 n 递增时，j 以相同的方式从 n 向 0 递减。因此，内部循环应该在 n/2 次迭代后停止。 因此，我建议时间复杂度为 O(n*n/2) 或简化为 O(n^2)。 我对吗？提前致谢。
让我们看看循环是怎样的 运行ning:
- i=0 => j 将 运行 从 1 到 n => n 次
- i=1 => j 将 运行 从 2 到 n => (n-1) 次
- i=2 => j 将 运行 从 3 到 n => (n-2) 次
- .................................................
- i=n-1 => j 将 运行 从 n 到 n => 1 次
所以将所有项相加，我们得到
n + (n-1) + (n-2) + .... + 1 = n*(n+1)/2
这等于 O(n^2)。所以是的，你的结论是正确的。