3 방향 Quicksort Big-O Bound

Question

3 방향 Quicksort (이중 피벗 퀵 소트)의 경우 Big-O 경계를 찾는 방법은 무엇입니까? 누구든지 그것을 파생시키는 방법을 보여줄 수 있습니까?

Answer 1

을 증명 알고리즘의 복잡성과 을 찾는 사이에 미묘한 차이가있다. 당신이 미트로 할 수 으로

찾을이 알고리즘의 복잡성, 다른 대답했다 : 당신이 평균, 당신은 크기 n/3의 3 개의 작은 문제가 크기 n의 문제를 분리 것을 알고, 당신이 그렇게 크기가 1 인 문제에 대해 평균적으로 log_3 (n)`단계를 거치게됩니다.경험을 통해이 접근법에 대한 느낌을 갖기 시작하고 관련된 하위 문제와 관련하여 알고리즘을 복잡하게 추론 할 수 있습니다. 으로

이 알고리즘은 평균 경우 O(nlogn)에서 실행 증명, 당신은 Master Theorem를 사용합니다. 이를 사용하려면 배열을 정렬하는 데 소요 된 시간을 제공하는 재귀 수식을 작성해야합니다. 우리가 말했듯이, 크기 배열 n을 정렬하는 것은 크기가 n/3 인 3 개의 배열과 그것들을 만드는 데 걸린 시간을 정렬하는 것으로 분해 될 수 있습니다.

T(n) = 3T(n/3) + f(n) 

T(n)가 (실제로 필요한 기본 작업의 수) 크기 n의 입력 해상도 "시간"을 제공하는 기능이다

및 f(n)가 필요한 "시간"을 제공합니다 : 이것은 다음과 같이 쓸 수있다 문제를 하위 문제로 나눕니다.

3 방향 퀵 정렬의 경우 f(n) = c*n 배열을 검토하기 때문에 각 항목을 배치 할 위치를 확인하고 결국 교환을 수행하십시오. 이것은 (우리의 경우 k = 0에서) 일부 k >= 0에 대한 f(n) = O(n^(log_b(a)) log^k(n)) 다음

T(n) = O(n^(log_b(a)) log^(k+1)(n))) 

이 a = 3 및 b = 3으로 (우리가 재발 관계, T(n) = aT(n/b)에서 이러한 얻을) 경우,이

로 단순화한다고하는, Case 2 of the Master Theorem에서 우리를 배치

T(n) = O(n log n) 

그리고 증명입니다.

Answer 2

글쎄, 같은 증명이 실제로 적용됩니다.

각 반복은 배열을 3 개의 하위 목록으로 나눕니다. 평균적으로이 하위 목록의 크기는 각각 n/3입니다.
따라서 반복 횟수는 log_3(n)입니다. 도착할 때까지 (((n/3) /3) /3) ... 횟수를 찾아야하기 때문입니다. 이것은 당신에게 공식을 준다 :

n/(3^i) = 1 

어느 것이 i = log_3(n)에 만족한다.

각 반복은 여전히 ​​모든 입력을 처리하지만 (다른 하위 목록에 있음) - quicksort와 동일하며 O(n*log_3(n))을 제공합니다.

log_3(n) = log(n)/log(3) = log(n) * CONSTANT부터 평균 실행 시간은 O(nlogn)입니다.

하위 목록의 크기를 계산하는 데 더 비관적 인 방법을 사용하더라도 최소 균일 분포를 취하여도 여전히 1/4 크기의 첫 번째 하위 목록, 크기 1/2의 두 번째 하위 목록, 마지막 1/4 크기 (최소 및 최대 균일 분포)의 하위 목록은 log_k(n) 반복 (다른 k> 2)으로 다시 부패하여 전체적으로 O(nlogn)이됩니다. 각각의 반복이 몇 가지 상수, N_1을 C_1를 들어, 각 n>N_1를 들어, 실행하는 데 최대 c_1* n 작전 소요
:

---

는 공식적으로, 증거는 무엇인가있을 것입니다. (큰 O 표기법의 정의와 각 반복이 재귀를 제외하고 O(n)이라는 주장. 이것이 사실 인 이유를 스스로 설명하십시오. 여기에서 "반복"은 특정 "수준"에서 알고리즘에 의해 수행 된 모든 반복을 의미하며 단일 재귀 호출).

위에서 볼 수 있듯이, 당신은

이제

, 우리는 알고리즘의 실행 시간 T(n)는 것을 얻을 log_3(n) = log(n)/log(3) 반복 평균 경우에 (, 비관적에 대한 동일한 원칙을 사용할 수 있습니다 여기에 낙관적 버전을 복용)이 있습니다

definition of big O notation 바이

for each n > N_1: 
T(n) <= c_1 * n * log(n)/log(3) 
T(n) <= c_1 * nlogn 

, 그것은 T(n)가 M = c_1N = N_1과 함께 O(nlogn) 인 것을 의미한다.
QED