我試圖用下面的偽代碼來理解算法的時(shí)間復(fù)雜度：讓 nums 有數(shù)字的 ArrayListsort(nums)while(nums.size() > 1) { // remove two elements nums.remove(0); nums.remove(0); nums.add(some_number); sort(nums);}sort(nums)是(N)Log(N)。 nums.remove(0)是O(N) nums.add()是O(1)現(xiàn)在這個(gè)算法的時(shí)間復(fù)雜度是多少。
1 回答
慕婉清6462132
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超2個(gè)贊
最終的復(fù)雜性是O(n2 log n)因?yàn)槟鷪?zhí)行了n多次操作O(n log n)。
請(qǐng)記住，估計(jì)復(fù)雜度 ( O(...)) 與建立操作總數(shù)不同（通常時(shí)間函數(shù)T(...)由操作總數(shù)給出），它們是兩個(gè)不同的概念。算法分析是一個(gè)很好的介紹
因此，O(...)符號(hào)是上限，但卻T(...)是真實(shí)的步驟。
您可以嘗試精確計(jì)算T函數(shù)，也可以通過改進(jìn) 來降低上限O，但它們始終是不同的函數(shù)，這O適用于所有可能條目的最壞情況。
在您的代碼中，我們不知道T排序函數(shù)，只有它們的上限是O(n log n)，那么：
T(n) ≤ O(n log n) + T(3) + O((n - 1) log (n - 1)) + T(3) + O((n - 2) log (n - 2) + ...
T(n) ≤ O(n log n) + n T(3) + n O(n log n)
^^^^^^^^^
在這里，我們無法準(zhǔn)確定義、 、 ...T上的排序操作，這就是為所有這些操作建立更高級(jí)別的原因。然后：n-1n-2O(n log n)
T(n) ≤ O(n log n) + n T(3) + n O(n log n)
T(n) ≤ O(n log n) + O(n) + O(n2 log n)
T(n) ≤ O(n2 log n)
在第二個(gè)表達(dá)式中，我們有固定數(shù)量的上限，在這種情況下，上限將是上限中的最高者。
（刪除、刪除和添加 is T(3)，goto比較被忽略）
添加回答
舉報(bào)
0/150
提交
取消