内循环的时间复杂度从 0 到 i
Time complexity for inner loop from 0 to i
在实践测试中获得时间复杂度分析的代码：
for i in 0..n-1:
for j in 0..i:
答案将其复杂度写为 O(n^2)，并解释说两个循环的复杂度均为 O(n)。我很困惑为什么这不是 O(n!)，因为内部循环将首先 运行 0 次，然后是 1、2、3 等等，直到 n-1 次。
内部循环将 运行 O(Sigma(n)) 次或 O(n^2)。
如果
- 第一次迭代运行s 0次，最后一次迭代n-1次，
- 第二次迭代运行s 1次和倒数第二n-2次,
- 从最后n-3次到第二次的第三次迭代，
等等
然后他们平均到 (n-1) 发生 (n/2) 次 - 或者 O(n^2)
在实践测试中获得时间复杂度分析的代码：
for i in 0..n-1:
for j in 0..i:
答案将其复杂度写为 O(n^2)，并解释说两个循环的复杂度均为 O(n)。我很困惑为什么这不是 O(n!)，因为内部循环将首先 运行 0 次，然后是 1、2、3 等等，直到 n-1 次。
内部循环将 运行 O(Sigma(n)) 次或 O(n^2)。
如果
- 第一次迭代运行s 0次，最后一次迭代n-1次，
- 第二次迭代运行s 1次和倒数第二n-2次,
- 从最后n-3次到第二次的第三次迭代， 等等
然后他们平均到 (n-1) 发生 (n/2) 次 - 或者 O(n^2)