Big-O for While循環

我有這個算法，我試圖計算它的複雜性。Big-O for While循環

A = {a_1, a_2, a_3, ...} 
w = 0 
while A != empty 
    a' = argmin(A) #a' is the element with smallest y_a 
    if (N_a' + w > C) 
     A = A - {a'} 
    else 
     x_a' = x_a' + 1 
     w = w + N_a' 
     Update the y_a' value in A using x_a'

A是一組，並且如果不滿足條件（N_a' + w > C）是真，我們從該組直到集合爲空除去的元素。我知道該算法運行至少O(n)，但如果if語句爲false，它可以運行更多。假設最後一行（更新）需要一個固定的時間。

如何計算這裏的複雜度？

來源

2017-08-05 Self

即使你總是選擇當時的情況，由於'min（A）'和A操作的收縮，努力超過O（n）。他們通常會拿O（log n）。沒有更多的信息，關於其他情況就無從談起。如果你不走運，並且每當你有一個無限循環時都會被採取。 – Henry

由於'C'的值，它不能是無限循環。在某些時候，當我們到達'C'時，循環將終止。 – Self

除非N_a'爲零或負數;-) – Henry

我們首先確定then和else分支在最壞情況下可以運行的頻率。在當時的分支中，集合A變小了一個元素，所以它只能執行n次（其中n是A中元素的初始數量）。 else分支最多可以執行C次（取N_a'= 1，它必須> = 1）。 C是一個常數，所以這是O（1）。因此迭代總數爲O（n）。

臨界點現在是用於A的數據結構。必須支持三種操作：查找最小值，刪除最小元素以及最後一行中的更新。當我們選擇最小堆時，這些操作中的每一個都可以在O（log n）中完成。請注意，在這種情況下，更新是而不是 O（1）時間。總運行時間現在是O（n log n）。

樸素最小搜索（即對A使用無序數組）使得操作min，remove元素，並分別更新O（n），O（1）和O（1）。總運行時間因此將是O（n * n）。

使用有序數組來表示A，我們分別得到了O（1），O（1）和O（n）的運行時間。最小搜索O（1）操作爲每次迭代執行，所以O（n）次。刪除elemnt O（1）操作在then分支中，所以執行O（n）次，更新O（n）操作在else分支中，所以執行O（1）次。全部一起給出O（n）的運行時間。但是，如果集合必須在開始時進行排序，我們再次處於O（n log n）。

來源

2017-08-07 04:43:49 Henry

非常明確的分析和解釋，但我會回來與你討論。 – Self

Big-O for While循環

回答

相關問題