這段代碼片段的時間複雜度是多少？

我在我的程序中使用這種算法：這段代碼片段的時間複雜度是多少？

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

吧？那三個環都在一起呢？

來源

2011-11-28 infoSyStem

這只是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）

來源

2011-11-28 12:34:04 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 - 感謝您的糾正，我更新了答案 – Vitaliy

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

enter image description here

來源

2014-03-30 16:02:12

這段代碼片段的時間複雜度是多少？

回答

相關問題