这段代码的时间复杂度是多少？

Question

我在我的程序中使用了这个算法：

for( i=0 ; i<N ; i++ )

  for( j=i+1 ; j<N+1 ; j++ )

     for( k=0 ; k<i ; k++ )

          doWork();

有人能帮我找到这段代码的时间复杂度吗？我猜前两个循环的复杂度是

N*(N+1)/2 

没错？那三个循环一起怎么办？

- infoSyStem

---

在简单的分析中，您会省略任何常数乘数和加数，这实际上会使您得到O(N³)。在这种特殊情况下，可能有兴趣进行摊销运行时间分析，这要困难得多。;)因此，请确保您真正需要了解它的确切含义。 - Till Helge

Answer 1

感谢 @Tim Meyer 纠正我：

简单的方程式给出了以下序列（N= 0,1,2,3,4,5,6,7,8...）：0、0、1、4、10、20、35、56、84......，可以用以下公式解决：

u(n) = (n - 1)n(n + 1)/6 

因此，它将具有O((N - 1)N(N + 1)/6)的时间复杂度，可以简化为O(N^3)

- Vitaliy

---

这并不是100%正确的，因为对于N = 0和N = 1，doWork()将不会被调用。然后对于N = 2,3,4,5,..，该系列将是1,4,10,20,.. 因此它将是(N-1)*(N)*(N+1)/6，即(N^3-N)/6。通常你可以简化为O(N^3)，因为这是该方程中的主导因素。 - Tim Meyer

@Tim Meyer - 感谢您的纠正，我已经更新了答案。 - Vitaliy

Answer 2

正式来说，你可以这样做：

- Mohamed Ennahdi El Idrissi