我試圖用下面的偽代碼來理解算法的時間復雜度：讓 nums 有數字的 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)現在這個算法的時間復雜度是多少。
1 回答
慕婉清6462132
TA貢獻1804條經驗 獲得超2個贊
最終的復雜性是O(n2 log n)因為您執行了n多次操作O(n log n)。
請記住，估計復雜度 ( O(...)) 與建立操作總數不同（通常時間函數T(...)由操作總數給出），它們是兩個不同的概念。算法分析是一個很好的介紹
因此，O(...)符號是上限，但卻T(...)是真實的步驟。
您可以嘗試精確計算T函數，也可以通過改進 來降低上限O，但它們始終是不同的函數，這O適用于所有可能條目的最壞情況。
在您的代碼中，我們不知道T排序函數，只有它們的上限是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)
^^^^^^^^^
在這里，我們無法準確定義、 、 ...T上的排序操作，這就是為所有這些操作建立更高級別的原因。然后：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)
在第二個表達式中，我們有固定數量的上限，在這種情況下，上限將是上限中的最高者。
（刪除、刪除和添加 is T(3)，goto比較被忽略）
添加回答
舉報
0/150
提交
取消