給定代碼的複雜性？

我試圖找出作爲問題大小n的函數的給定代碼的複雜性。給定代碼的複雜性？

sum = 0; 

if (EVEN(n)) 
    for (i = 0; i < n; i++) 
     if (i%2 == 0) 
     O(logn) 
     else 
     sum ++; 
else 
    sum = sum + n;

這是我的答案，但我不知道我是否做得正確。

sum=0; is equal to O(1)。

第一個if else循環由嵌套for循環組成，並帶有嵌套if語句。所以它將是for循環內的代碼的n倍。由於它的if語句並且將是塊1或塊2.由於O(logn)比sum ++慢，因此它是O(1)它是O(logn)。所以它是O(n)*O(logn)。

因此最終答案是O(1) + n*O(logn)。它是否正確？？

來源

2012-10-09 Steve S

我在想最好的情況和平均情況。這是我的解釋，這聽起來正確嗎？現在我們來考慮最好的情況，其中n不是偶數。由於n甚至不是第一個if語句內部的代碼不會執行。所以我們需要看代碼sum = sum + n。這是O（1）的運行時間。把它加起來就是O（1）+ O（1）= 2 * O（1），它等於O（1）。所以最好的情況是O（1）。平均值爲O（n * log（n））+ O（1）/ 2 –

是的，O（nlog（n））是複雜度。

來源

2012-10-09 18:38:05 FSP

我在想最好的情況和平均情況。這是我的解釋，這聽起來正確嗎？現在讓我們考慮最好的情況，其中n不是偶數。由於n甚至不是第一個if語句內部的代碼不會執行。所以我們需要看代碼sum = sum + n。這是O（1）的運行時間。把它加起來就是O（1）+ O（1）= 2 * O（1），它等於O（1）。所以最好的情況是O（1）。平均值爲O（n * log（n））+ O（1）/ 2 –

如果你在談論最差的運行時間，Yeap似乎是正確的。您可以將O(n)*O(logn)重寫爲O(n*log(n))。

來源

2012-10-09 18:31:04

給定代碼的複雜性？

回答

相關問題