对嵌套的 for 循环如何既是 O(n!) 又是 O(n^2) 感到困惑
Confused about how nested for loops could be both O(n!) and O(n^2)
假设有一个简单的嵌套 for 循环：
for i in range(0, n):
for j in range(0, n):
print(i*j)
几乎每个人都很容易将其视为 O(n^2)。现在，如果我们修改嵌套的 for 循环：
for i in range(0, n):
for j in range(i, n):
print(i*j)
它会按照 n x n-1 x n-2 ... x 1 的路线发展，对吧？这将是相同的 n!，这应该是一个可怕的上限。那我在这里错过了什么？为什么 for 循环的较小版本明显跳过循环的几次迭代导致更糟糕的大 o 表示法？
那个计算应该是n + n-1 + n-2 ... + 1，也就是O(n²)。
for i in range(0, n):
for j in range(i, n):
print(i*j)
- 在外循环的第一次迭代中，内循环执行n次操作。
- 第二个，n-1次操作。
- 第三个，n-2次操作
- ...等等，直到内循环只进行 1 次迭代。
n + n-1 + n-2 + ... + 1 = O(n^2)，乘法从何而来？
请注意，从学究意义上讲，O(n^2) 也是 O(n!)。也就是说，O(n!) 包括 O(n^2)（然后是一些）的函数。
我也是新来的。根据我的理解，我认为
for i in range(0,n) -> n 次
对于范围 (i,n) 中的 j -> n-i 次
因为只有 2 个循环，这意味着 n * (n-i) 用于整个操作。它应该只是 O(n^2).
假设有一个简单的嵌套 for 循环：
for i in range(0, n):
for j in range(0, n):
print(i*j)
几乎每个人都很容易将其视为 O(n^2)。现在，如果我们修改嵌套的 for 循环：
for i in range(0, n):
for j in range(i, n):
print(i*j)
它会按照 n x n-1 x n-2 ... x 1 的路线发展，对吧？这将是相同的 n!，这应该是一个可怕的上限。那我在这里错过了什么？为什么 for 循环的较小版本明显跳过循环的几次迭代导致更糟糕的大 o 表示法？
那个计算应该是n + n-1 + n-2 ... + 1，也就是O(n²)。
for i in range(0, n):
for j in range(i, n):
print(i*j)
- 在外循环的第一次迭代中，内循环执行n次操作。
- 第二个，n-1次操作。
- 第三个，n-2次操作
- ...等等，直到内循环只进行 1 次迭代。
n + n-1 + n-2 + ... + 1 = O(n^2)，乘法从何而来？
请注意，从学究意义上讲，O(n^2) 也是 O(n!)。也就是说，O(n!) 包括 O(n^2)（然后是一些）的函数。
我也是新来的。根据我的理解，我认为
for i in range(0,n) -> n 次 对于范围 (i,n) 中的 j -> n-i 次
因为只有 2 个循环，这意味着 n * (n-i) 用于整个操作。它应该只是 O(n^2).