分析大哦符號僞代碼

我在解決算法分析問題時遇到了麻煩。我似乎沒有確定線性或平方算法，但完全失去了nlogn或logn算法，這些似乎主要來自while循環？這是我一直在尋找一個例子：分析大哦符號僞代碼

Algorithm Calculate(A,n) 
Input: Array A of size n 
t←0 
for i←0 to n-1 do 
    if A[i] is an odd number then 
     Q.enqueue(A[i]) 
    else 
     while Q is not empty do 
     t←t+Q.dequeue() 
while Q is not empty do 
    t←t+Q.dequeue() 
return t

我最好的猜測是用於循環被執行n次，其嵌套while循環Q倍使NQ和最終while循環也Q倍導致O（NQ + Q ）這是線性的？

來源

2010-04-09 drunkmonkey

隊列是如何實現的？ – yassin 2010-04-09 15:34:38

我會想象如果它沒有指定，可以假定隊列操作（入隊和出隊）在'O（1）'中運行。 – FrustratedWithFormsDesigner 2010-04-09 15:36:44

嗨，它沒有在問題中指定我假設que方法將是O（1）。謝謝 – drunkmonkey 2010-04-09 15:39:10

首先，讓我們假設Q最初是空的。

Q只會以與主循環執行相同的速度增長。例如，如果我們已經迭代了3次以上，那麼Q最多隻有3個元素。所以當inner while循環執行時，它最多隻能執行到'i'的當前值。這意味着內部循環在n^2上不是真實的情況（這不是你聲稱的東西）。然而，由於Q最多隻能是'我'元素大，因此我們知道O（計算）< = O（2N）。而且由於O符號中我們確實不關心標量，那麼它就是O（N）。

除非我錯了:)

來源

2010-04-09 15:40:41 Torlack

我認爲最糟糕的情況是如果Q增長到n的大小，但要發生這種情況，內部循環只能在for循環的第n次迭代中執行，所以它應該是O（2N ），所以是的，O（n）聽起來是對的。 – FrustratedWithFormsDesigner 2010-04-09 15:43:21

分析大哦符號僞代碼

回答

相關問題