thomas - introduction to algorithms 번역 pdf




Cormen의 알고리즘 소개(Introduction to Algorithms) (4)

나는 그것이 옳다고 생각한다. 그러나 나는 그것을 증명할 적절한 방법이 conditionnal expectations를 사용하는 것이라고 생각한다 :

모든 X와 Y에 대해 E [X] = E [E [X | Y]]

그렇다면 귀하의 경우 :

E (i + 1) = E [x (i + 1)] = E [E [x (i + 1) (i)] = E [SUM (k) / (1 + i) + x (i)] =

두 번째 성명서에 관하여 :

만약 :

E (n) = n * (n-1) / 4.

n / 4 + 2 * n / 4 = (n-1) * n / 4 + n / 2 = E (n + 1) n) + n / 2

그래서 n * (n-1) / 4. 모든 n> = 2에 대한 재귀 관계를 검증하고 n = 2에 대해 검증한다.

따라서, E (n) = n * (n-1) / 4

희망을 당신의 문제를 이해하고 도움이됩니다.

A [1 .. n]을 n 개의 distinct 번호 배열로합시다. i <j와 A [i]> A [j] 인 경우, 쌍 (i, j)는 A의 역변환이라고 부른다. 역변환에 대해서는 2-4 문제를 참조한다. A의 각 원소가 선택된다고 가정 해보자. 무작위로, 독립적으로, 그리고 균일하게 범위 1에서 n까지. 지표 임의 값을 사용하여 예상 역전 횟수를 계산하십시오.

문제는 코멘 (Cormen)의 알고리즘 개론 (Introduction to Algorithms)의 연습 문제 5.2-5에서 비롯됩니다. 다음은 재귀 적 솔루션입니다.

x (i)가 [1.i]의 역행렬의 수이고 E (i)가 x (i)의 기대 값이라고 가정하면 E (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 (n) = (n-1 + n-2 + ... + 2) / 2 + 0.5 = n * (n-1) / 4 이렇게하면 재귀 적으로 E .

위의 공제가 옳은 것처럼 보이지만 나는 아직도 그 점을 잘 모릅니다. 그래서 나는 그것을 여기에서 나눕니다.

잘못된 것이 있으면 저를 시정하십시오.


또 다른 솔루션은 "지표 임의 변수"를 사용하지 않지만 훨씬 더 간단합니다.

모든 수는 구별되기 때문에 모든 요소 쌍은 역변환 ( 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부터 n 까지의 범위에있는 숫자 A 의 모든 배열에 대해 n+1 에서 각 숫자를 뺄 때 얻은 배열로 ~A 를 정의하십시오. 예를 들어 A[2,3,1] 이면 ~A[2,1,3] 입니다.

이제 A 에있는 순서대로 A 숫자의 쌍에 대해 ~A 의 해당 요소가 순서가 맞지 않는 것을 관찰하십시오. (두 숫자가 순서가 바뀌기 때문에 쉽게 표시 할 수 있습니다.)이 매핑은이 문맥보다 덜 ~보다 큰 대칭 (이중성)을 명시 적으로 보여줍니다.

따라서 어떤 A 에 대해서도 역전의 수는 ~A 역전되지 않은 역의 수와 같습니다. 그러나 가능한 모든 A 대해 정확히 하나 ~A 가 해당합니다. 숫자가 균등하게 선택되면 A~A 가 똑같이 나타날 수 있습니다. 따라서 A 에서의 예상 역전 수~A 의 예상 역전 수와 동일합니다. 왜냐하면이 기대치가 정확히 같은 공간에서 계산되기 때문입니다.

따라서 A 에 예상되는 역전 횟수는 예상되는 역전 횟수와 같습니다. 이러한 기대치의 합은 상수 n*(n-1)/2 또는 총 쌍 수 인 합계의 기대치입니다.

[업데이트 2]

보다 단순한 대칭성 : n 원소 중 임의의 배열 A 에 대해 ~A 를 같은 원소로 역순으로 정의하십시오. A i 위치에있는 요소를 ~A 있는 n+1-i 위치의 요소와 연결합니다. 즉, 각 요소를 역 배열로 연결합니다.

이제 A 모든 반전은 위의 Update 1의 구성과 마찬가지로 ~A 의 비 반전과 연관됩니다. 그래서 같은 주장이 적용됩니다 : A 의 역전의 수는 ~A 의 역전의 수와 같습니다; A~A 모두 똑같이 가능한 시퀀스입니다. 기타

직감의 요점은 "미만"과 "보다 큼"연산자는 서로의 이미지를 미러링하는 것인데, 이는 인수 1을 부정하거나 (Update 1에서와 같이) 또는 교체하여 볼 수 있습니다 (Update 2). 따라서 미러를 통해 특정 어레이를보고 있는지 여부를 알 수 없기 때문에 예상되는 역전 반전 횟수와 비 반전 횟수는 동일합니다.


위의 Aman의 답과 비슷하지만 더 단순한 경우 라 할지라도 ...

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.

지표 임의 변수 사용 :

  1. X = 역전의 수와 같은 확률 변수 라하자.
  2. A [i]와 A [j]가 반전 쌍을 이루면 Xij = 1, 그렇지 않으면 Xij = 0이됩니다.
  3. 반전 쌍의 수 = 1보다 큰 합 <= i <j <= n of (Xij)
  4. 이제 P [Xij = 1] = P [A [i]> A [j]] = (n은 2를 선택) / (2! * n은 2를 선택) = 1/2
  5. E [Xij] = n (n-1) / 4의 ij와 같은 모든 ij 쌍에 걸친 Eij [ij]




algorithm