如何在氣泡排序中找到預期互換次數優於O（n^2）時間

我被困在問題上http://www.codechef.com/JULY12/problems/LEBOBBLE 這裏需要找到預期互換次數。如何在氣泡排序中找到預期互換次數優於O（n^2）時間

我試過一個O（n^2）解決方案，但它超時。

的代碼是這樣的：

swaps = 0 
for(i = 0;i < n-1;i++) 
    for(j = i+1;j<n;j++) 
    { 
     swaps += expected swap of A[i] and A[j] 
    }

由於元件的概率不同，因此需要對每對比較。所以根據我上面的代碼片段必須是最有效的，但它是超時。

它可以在O（nlogn）中完成，或者它比O（n^2）更好。如果可能，給我任何提示。

來源

2012-07-10 user1515905

我投下了因爲它從當前運行的比賽中的問題。 – kilotaras 2012-07-10 20:41:33

也可以在O（n logn） – kilotaras 2012-07-10 20:42:05

^如何做？謹慎給我們一個提示？我真的好奇，並不在意比賽：D – 2012-07-10 21:36:35

好的，讓我們來思考一下。

我們認識到，每個數字最終都要與它後面的每個數字相互交換，遲早會少於它。因此，一個給定數量的交換總次數是它之後的總數量小於它的總數量。但是，這仍然是O(n^2)時間。

對於氣泡排序外部循環的每一次通過，都會將一個元素置於正確的位置。在不失一般性的情況下，我們會說每傳遞一次，剩下的最大元素就被排序到列表的末尾。

所以，在外循環的第一遍中，最大的數字是放在最後。這需要q掉期，其中q是數量開始遠離最終頭寸的頭寸數目。

因此，我們可以說，它會採取q + Q + ... + Q _ň掉期來完成這個冒泡排序。但是，請記住，每次交換時，一個數字將被選爲離其最終位置較近的一個位置或離其最遠的一個位置。在我們的具體情況中，如果某個數字位於較大數字的前面，並位於其正確位置之前或之前，則需要再進行一次交換。但是，如果一個數字位於更大的數字之後，並且位於正確的位置之後，則需要少一個交換。

我們可以看到，這是用下面的例子真：

5 3 1 2 4 
=> 3 5 1 2 4 
=> 3 1 5 2 4 
=> 3 1 2 5 4 
=> 3 1 2 4 5 
=> 1 3 2 4 5 
=> 1 2 3 4 5 (6 swaps total)

「5」移動4位。「3」移動1個空格。「1」移動2個空格。「2」移動2個空格。「4」移動1個空格。總共：10個空格。

請注意，3位於5之後並位於其正確位置的前方。因此需要再換一次。 1和2在3和5之後 - 需要4次掉期。 4在5之後並且在其正確位置之後，因此需要少一次交換。我們現在可以看到6的預期值與實際值相符。

我們可以計算Σ q首先對列表進行排序，在排序時將每個元素的原始位置保留在內存中。這可能在O(nlogn + n)時間。

我們也可以看到其他數字背後的數字是什麼，但這是不可能的，比在O(n^2)的時間更快。但是，我們可以獲得更快的解決方案。

每次交換都有效地將兩個數字號碼需求移動到其正確的位置，但是一些交換實際上什麼都不做，因爲最終與每個數字進行交換後，它會小於它，而另一個則會變得更遠或更晚。我們前面的例子中的第一個交換，因此在「3」和「5」之間是我們例子中唯一的例子。

我們必須計算出有多少交換的總數。這只是對讀者的一個練習，但這裏有一個最後的提示：你只需要遍歷列表的前半部分。儘管對於給定數量的這個數字仍然是最後的O(n^2)，但我們只需要在列表的前半部分執行O(n^2)的操作，從而使得整體數字更快。

來源

2012-07-10 21:22:23

使用分而治之

分：序列n個大小尺寸的兩個列表N/2 治之：計數遞歸兩個列表結合：這是一招部分（這樣做以線性時間）

聯合使用合併和計數。假設這兩個列表是A，B，它們已經排序。從A，B生成輸出列表L，同時還計算反轉次數（a，b），其中a是-A，b是-in B，a> b。

這個想法與merge-sort中的「merge」類似。將兩個排序列表合併到一個輸出列表中，但我們也計算倒置。

每次將a_i附加到輸出時，都不會遇到新的反轉，因爲a_i小於列表B中的所有內容。如果將b_j附加到輸出中，則它小於A中剩餘的所有項，（A，B） ;並列數（A，B） ;合併和計數（A，B） ;合併和計數（A，B） ; A，B兩個輸入列表（排序） ; C輸出清單 ; i，j當前指向每個列表的指針，從開頭開始;由i指向的a_i，b_j元素，j ;計數反轉的數目，最初爲0

而A，B！=空附加分鐘（A_I，b_j）至C 只要當A J ++ 別的剩餘b_j < A_I 計數+ =數目元件的我+ + ;現在一個列表爲空追加列表到C 返回計數的剩餘部分，C

隨着合併和計數，我們可以按照如下設計計反演算法：

排序和計數（ L）如果L具有一個元件返回0 別的分L放入A，B （RA，A）=排序和計數（A）（RB，B）=排序和計數（B）（r，L）=合併和計數（A，B） return r = rA + rB + r，L

T（n）= O （n lg n）

來源

2015-11-25 23:52:06

如何在氣泡排序中找到預期互換次數優於O（n^2）時間

回答

相關問題