정수 파티션이있는 빠른 정렬 알고리즘

Question

빠른 정렬 알고리즘에 대한 질문이 생겼습니다. 이것은 중국 대학의 데이터 구조에 대한 2010 - 중간 고사에서 나옵니다.

빠른 정렬에서 파티션 절차를 C 시간 (일정 시간 소요)으로 가정합니다. 무작위 데이터를 입력으로 사용하는 경우 무작위 - 빠른 정렬의 순서 (시간 복잡도)는 무엇입니까?

누구나 이런 방식으로 시간 복잡성을 설명 할 수 있습니까?

편집 :

이 관계를 계산합니다. 내 일은 옳은가요? 누구든지 나를 명확히 할 수 있니?

Best Case: T(n)=2T(n/2)+C= Theta (n) 

Worst Case: T(n)=2T(n-1)+C= Theta (n) 

Answer 1

예상 실행 시간 : 예상 값 T(n)을 찾고 있습니다. 따라서 실행 시간에 대한 임의 변수는 T(n)이라고합시다. 파티션에 해당하는 각각의 n 가능한 결과가 있습니다 이들의

T(0) + T(n-1) + c 
T(1) + T(n-2) + c 
... 
T(n-1) + T(0) + c 

하나가 뽑힐 것입니다가, X(i) = 1 if T(i) + T(n - i - 1) + c가 선택됩니다하자, 그렇지 않으면 0. T(n)의 재발은 다음과 같이 쓸 수있다 :

T(n) = X(0)(T(0) + T(n-1) + c) + ... + X(n-1)(T(n-1) + T(0) + c) 

지금 기대를 계산하기 위해, 우리는 쓰기 :

E(T(n)) = E(X(0)(T(0) + T(n-1) + c) + ... + X(n-1)(T(n-1) + T(0) + c)) 
      = (1/n)E(2T(0) + 2T(1) + ... + 2T(n-1) + cn) 
      = (2/n)(E((T(0)) + ... + E(T(n-1))) + c. 

세 번째 라인은 기대의 선형성을 얻었다. 이 시점에서 우리는 E(T(i))에 대한 답을 추측하고 유도를 사용하여이를 증명합니다. 이 기술을 대체라고합니다. E(T(i)) <= Ai, A > 0 및 1 <= i < n에 대한 : 추측

• .
• 베이스 : i = 1 인 경우 배열은 이미 정렬되어 있으므로 예상 실행 시간은 일정합니다.
• 유도 : E(T(n)) <= (2A/n)(n(n-1)/2) = A(n-1) <= An.

그래서 주장은 n. 예상 된 실행 시간은 O(n)입니다.