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

问题描述：

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

吧？那三个环都在一起呢？

这只是O（N^3）。 –

在一个简单的分析中，你会忽略任何不变的乘数和加数，这确实会给你带来O（N³）。在这种特殊情况下，分期运行时分析可能会很有趣，但这种分析要困难得多。 ;）所以确保你真的需要知道这一点。 –

答

由于@Tim迈耶指正：

简单方程给出（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）

它不是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 - 感谢您的纠正，我更新了答案 – Vitaliy

答

形式上，你可以做foll欠款：

enter image description here

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

相关推荐