預期的反演次數 - 從簡介到科爾算法

設A [1..n]是一個包含n個distinct數字的數組。如果我和A [i]> A [j]，那麼這個對（i，j）被稱爲A的反演。（關於反演的更多內容，請參見問題2-4）。假設選擇A的每個元素隨機地，獨立地且均勻地從1到n的範圍。使用指標隨機變量來計算預期的反演次數。預期的反演次數 - 從簡介到科爾算法

的問題是從鍛鍊5.2-5在介紹由Cormen到算法。這裏是我的遞歸求解：

假設x（i）是a [1..i]中的倒數的個數，E（i）是x（i）的期望值，則E（i +1）可以計算如下：
圖片我們有i+1的位置來放置所有的數字，如果我們把i + 1放在第一個位置上，那麼x（i + 1）= i + x（i）;如果我們在第二個位置上放置i + 1，則x（i + 1）= i-1 + x（i），...，所以E（i + 1）= 1 /（i + 1）* sum（k）+ E（i），其中k = [0，i]。最後我們得到E（i + 1）= i/2 + E（i）。因爲我們知道E（2）= 0.5，所以遞歸地得到：E（n）=（n-1 + n-2 + ... + 2）/ 2 + 0.5 = n *（n-1）/4。

雖然扣除上述似乎是正確的，但我仍然不是很肯定。所以我在這裏分享。

如果有什麼問題，請糾正我。

來源

2011-10-18 Flybywind

請注意，這本書的第二版中的問題是不同的。 –

我認爲這是正確的，但我認爲正確的方式來證明它是使用conditionnal預期：

對所有的X和Y，我們有：E [X] = E [E [X | Y]

然後在您的情況：

的E（i + 1）= E [X（I + 1）] = E [E [X（I + 1）| （i）] = E [i（i）]] = E [i（i）] = i/2 + E（i）

關於第二語句：

如果：

E（N）= N *（N-1）/ 4。那麼E（n + 1）=（n + 1）* n/4 =（n-1）* n/4 + 2 * n/4 =（n-1）* n/4 + n/2 = E（n）+ n/2

因此n *（n-1）/ 4。驗證所有n> = 2的遞推關係，並驗證它對於n = 2

所以E（N）= N *（N-1）/ 4

希望我理解你的問題，它可以幫助

來源

2011-10-18 09:04:53

所有的解決方案似乎都是正確的，但問題是我們應該使用指標隨機變量。所以這是我的解決方案使用相同的：

Let Eij be the event that i < j and A[i] > A[j]. 

    Let Xij = I{Eij} = {1 if (i, j) is an inversion of A 

         0 if (i, j) is not an inversion of A} 

    Let X = Σ(i=1 to n)Σ(j=1 to n)(Xij) = No. of inversions of A. 

    E[X] = E[Σ(i=1 to n)Σ(j=1 to n)(Xij)] 

     = Σ(i=1 to n)Σ(j=1 to n)(E[Xij]) 

     = Σ(i=1 to n)Σ(j=1 to n)(P(Eij)) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(P(Eij)) (as we must have i < j) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(1/2) (we can choose the two numbers in 
              C(n, 2) ways and arrange them 
              as required. So P(Eij) = C(n, 2)/n(n-1)) 

     = Σ(i=1 to n)((n - i)/2) 

     = n(n - 1)/4

來源

2012-02-29 18:57:19

很好的答案，+1。只是要詳細說明P（Eij）部分：給定n個數字的方法填充2個點的總數是n（n-1）。現在假設所有n個數字都按升序排序。如果您選擇第一個數字，則將下一個（n-1）數字作爲創建反轉對的選項。如果你選擇第二個，那麼你有下一個（n-2）號碼作爲選項，等等。因此，創建倒數的總體方法是（n-1）+（n-2）+ ... + 2 + 1 = n（n-1）/ 2。所以你有P（Eij）= {n（n-1）/ 2}/{n（n-1）} = 1/2 –

我知道的太晚了，但是另一種觀察P （Eij）有兩種可能性：A [i]> A [j]或A [i] <= A [j]對於所有元素j A [j]爲0.5的概率它是所有這些概率的和，即對於i = 1，它是（n-1）* 0.5，對於j = 2，它是（n-2）* 0.5因此對於所有n，它是Σ（i = 1到n）（n - i）* 0.5 – SomeDude

另一種解決方案甚至更簡單，國際海事組織，雖然它不使用「指標隨機變量」。

由於所有的號碼是不同的，每對元件或者是一個反轉（i < j與A[i] > A[j]）或非反轉（i < j與A[i] < A[j]）。換句話說，每一對數字要麼是有序的，要麼是無序的。

因此，對於任何給定的排列，反轉加非反轉的總數只是對的總數，或n*(n-1)/2。

由於「小於」和「大於」的對稱性，預期的反轉次數等於預期的非反轉次數。

由於它們的總和的期望是n*(n-1)/2（對於所有排列不變），並且它們是相等的，所以它們各自爲一半或n*(n-1)/4。

[更新1]

顯然我「的‘小於’和‘大於’對稱」語句需要一些闡述。

對於範圍爲1號A的任何陣列通過n，定義~A作爲數組當你從n+1減去每個號碼你得到。例如，如果A是[2,3,1]，則~A是[2,1,3]。

現在，請注意，對於A中按順序排列的任何一對數字，~A的相應元素出現故障。（容易顯示，因爲否定兩個數字交換它們的順序。）該映射明確地顯示了小於和大於這個上下文之間的對稱性（二元性）。

因此，對於任何A，反轉次數等於~A中的非反轉次數。但是對於每一個可能的A，都只有一個~A;當統一選擇號碼時，A和~A的可能性相同。因此，A中預期的反演次數等於預期的反演~A，因爲這些預期是在完全相同的空間上計算的。

因此，A中的預期反演次數等於預期的非反轉次數。這些期望的總和就是總和的期望值，這是常數n*(n-1)/2，或總數對。

[更新2]

更簡單的對稱性：對於n元件的任何陣列A，定義~A爲相同的元件，但以相反的順序。將位於A的位置i處的元素與位置n+1-i處的元素關聯在~A中。（也就是說，將每個元素與它自己的相反陣列相關聯）。

現在A中的任何反轉都與~A中的非反轉相關，就像上面Update 1中的構造一樣。所以相同的論點適用：A中的反轉次數等於~A中的反轉次數; A和~A都是同樣可能的序列;等等

這裏直覺的一點是，「小於」和「大於」運算符只是彼此的鏡像，您可以通過否定參數（如更新1中）或通過交換（如更新2）。所以反轉和非反轉的期望數量是相同的，因爲你不能通過鏡像來判斷你是否正在查看任何特定的數組。

來源

2012-02-29 19:15:42 Nemo

你怎麼知道＃小於==＃大於？我不認爲他們說對稱證明了任何事情。 –

@KarolyHorvath我已經添加了一個更新來闡述。直覺很簡單，但形式化確實需要一些努力來精確地說話。謝謝。 – Nemo

可愛的減肥方法。 +1 –

使用指示符隨機變量：

設X =隨機變量，它是等於反轉的數目。
如果A [i]和A [j]形成一個反轉對，那麼令Xij = 1，否則Xij = 0。
反轉雙=薩姆數量超過1 < = I <Ĵ<（Xij）
現在P的= N [Xij = 1] = P [A [I]> A [j]的] =（N選擇2）/（2！* n選擇2）= 1/2
E [X] = E [所有ij對之和，使得iij對所有ij對進行求和，使得i = <j E [Xij = N（N - 1）/ 4

來源

2015-06-14 13:32:38

更簡單（類似於上面祖阿曼的答案，但也許更清晰）...

Let Xij be a random variable with Xij=1 if A[i] > A[j] and Xij=0 otherwise. 
Let X=sum(Xij) over i, j where i < j 

Number of pairs (ij)*:    n(n-1)/2 
Probability that Xij=1 (Pr(Xij=1))): 1/2 
By linearity of expectation**:  E(X) = E(sum(Xij)) 
              = sum(E(Xij)) 
              = sum(Pr(Xij=1)) 
              = n(n-1)/2 * 1/2 
              = n(n-1)/4 

* I think of this as the size of the upper triangle of a square matrix. 
** All sums here are over i, j, where i < j.

來源

2015-12-31 00:03:15

預期的反演次數 - 從簡介到科爾算法

回答

相關問題