算法时间复杂度的计算 T(n)

Question

我希望为您提供一些关于算法时间效率的解释，特别是T(n)。下面的算法并不是最有效的，但我认为这是一个很好的例子可以加以学习。我将逐行确认代码中操作总和，希望对您有所帮助。

伪代码：

 1.  Input: array X of size n
 2.  Let A = an empty array of size n
 3.  For i = 0 to n-1
 4.      Let s = x[0]
 5.      For j = 0 to i
 6.          Let sum = sum + x[j]
 7.      End For
 8.      Let A[i] = sum / (i+1)
 9.  End For
 10. Output: Array A

我的尝试计算 T(n)

 1.  1
 2.  n
 3.  n
 4.  n(2)
 5.  n(n-1)
 6.  n(5n)
 7.  -
 8.  n(6)
 9.  -
 10. 1

 T(n) = 1 + n + n + 2n + n^2 - n + 5n^2 + 6n + 1
      = 6n^2 + 9n + 2 

因此，T(n) = 6n^2 + 9n + 2 是我得出的结果，从中我推导出了 O(n^2) 的大O表示法。 在计算 T(n) 的基本操作时，我是否有任何错误？

编辑：... 在计算基本操作数时有没有错误？

- Josh

---

这是一个直接的双重循环，没有条件中断，所以它的时间复杂度为O(n^2)。 - Kerrek SB

谢谢，我有点怀疑它不是O(n^2)，只是对于T(n)之前的计算有点不确定。 - Josh

Answer 1

您的O(n^2)结果是正确的，并且由两个嵌套循环给出。我更喜欢像这样推导：

0 + 1 + 2 +  + (n-1) = (n-1)n/2 = O(n^2)

从观察嵌套循环中得出的结论。

- Jiri Kriz

Answer 2

我不太确定你的方法，但O(n^2)似乎是正确的。在第一次循环的每次迭代中，您都会对先前元素进行子循环。因此，第一次看1，第二次看2，然后看3，然后...最后看n。这相当于从1到n的总和，这给出了n^2的复杂度。

- Josh