確定while循環內部的函數的大-O

對於循環中循環內部的這種函數aFunction（）具有O（nlog（n））的大-o，如何確定最壞情況下的時間複雜度？確定while循環內部的函數的大-O

i ← 0 
while (i < n) 
    aFunction(...) 
    i ← i+1 
done

什麼是論據，他們是否依賴於像'我'或'n'這樣的東西？您的代碼示例太薄 – Leeor

由於它涉及算法時間複雜性並且不涉及實際的代碼，因此這看起來是無關緊要的。改爲考慮cs.stackexchange.com。 – dg99

想想這裏做了多少工作。每撥打aFunction需要時間O（n日誌n），你總共調用n次。總的來說，這使得總共有O個工作（總共工作時間爲0天）。

希望這會有所幫助！

2015-01-15 23:01:39 templatetypedef

不是這麼簡單。每個呼叫都需要'O（i log i）'。所以爲了確保你是對的，我們必須把所有的'i log i'從i = 1到n。（如果我正確理解OP的問題） – Everv0id

@ Everv0id從提供的僞代碼中，我無法判斷每次迭代時是否在'i'或'n'上調用'aFunction'。我認爲這是'n'，但你說得對，如果每次迭代都是'我'，那麼這裏需要更多的數學。 – templatetypedef

回答