Q

迭代循環 - 複雜性

2012-12-17 181 views -3 likes

-3

我寫了一個算法來查找鏈接列表中的重複項。
對於每個節點，我從列表頭開始迭代到當前節點，如果它是重複的，它將被刪除。迭代循環 - 複雜性

我算法的複雜性是什麼？

2012-12-17 socksocket

+0

對於每個項目，你似乎爲了查找重複項和remove.that意味着你有嵌套循環，複雜度是O（n^2）。如果你可以發佈你的代碼會更好。我從聲明中猜測你的邏輯。 –

A

回答

4

的算法的複雜度是Θ(n^2)最壞的情況下，因爲如果沒有愚弄，你迭代每個節點的線性增加的次數，從而導致總1 + 2 + .... + n總的讀入是Θ(n^2)（來自sum of arithmetic progression）

在最好的情況下的複雜性是Θ(n) - 如果所有元素都是受騙者的複雜性是Θ(n)，因爲在每次迭代名單縮小，這將導致至多2節點每次迭代中讀取，因此Θ(n)

2012-12-17 10:33:34 amit

相關問題