複雜性（計算大O）

我一直在研究我的教科書中有關計算算法的大O複雜性的一些問題。其中一個難題我沒有在後面回答，我會很感激任何輸入。複雜性（計算大O）

您有包含單詞列表長度爲n-1的含鏈表的陣列。每個鏈表首先被插入排序，然後使用鏈表中的第一個單詞，該數組被快速排序。這個算法的大O複雜度是什麼？

我已經知道：

遍歷一個鏈表爲O（n）插入排序是O（n^2）快速排序是（nlogn）

我只是不知道如何到去計算整個算法

2012-02-17 user1217222

因此，需要N^2插入到列表中，然後NLG（N）進行排序，你會做這N-1次（對吧？）所以我會說這是（N-1）* （n^2 + n * lg（n））=〜n^3 + n^2 * lg（n），那麼大的O（n^3）？ – macduff 2012-02-17 21:59:43

你的問題意味着該數組的大小爲n-1，並且所有鏈表都是大小n。那是對的嗎？ – hatchet 2012-02-17 22:17:34

的複雜性「每個鏈表是第一次插入排序」

這使得一個的O(n) * O(m^2)，或O(n*m^2)複雜 - 我們必須使用不同的字母，因爲每個列表的長度與列表數量無關。

「那麼該陣列被quicksorted」

這增加O(n log n)。

總計：O(n*m^2 + n log n)，簡化爲O(n*m^2)（n log n與n*m^2相比不顯着）。

來源

2012-02-17 22:01:19

我不是大O符號的專家，所以如果我錯了，不要太過於苛刻：p – 2012-02-17 22:01:35

從技術上講，你應該有O（max（nm^2，nlogn））。再次，Quicksort在最壞的情況下是O（n^2），所以除非這是一個平均情況分析，否則在回答O（max（nm^2，n^2））方面更爲正確。只是說。你想要一個最壞的O（nlogn）算法，嘗試合併或堆排序。 – Patrick87 2012-02-18 01:06:24

複雜性（計算大O）

回答

相關問題