"최악의 경우"quicksort를 시도하는 중

C에서 quicksort 구현을 구현했으며 성능을 저하시키는 데 필요한 입력을 파악하려고합니다. wikipedia 따르면"최악의 경우"quicksort를 시도하는 중

항상 이미 정렬 된 목록 또는 동일한 구성 요소의 목록에서 성능 저하 (N^2)이 방법은 결과에 피봇 같은 파티션 내의 마지막 요소를 선택.

그래서 시도해 보니 the following code이되었습니다. 피벗은 항상 마지막 요소이며 입력은 이미 정렬 된 목록입니다.

복잡성이 실제로 n^2라는 것을 증명하기 위해 각 반복에서 증가하는 전역 변수를 생성 한 다음 최종적으로 인쇄합니다.

가 나는 프로그램이 인쇄 것으로 예상 것 :

Done in 64 iterations

그러나, 28 번의 반복을했다. 어쩌면 "복잡성"이라는 용어에 대한 나의 이해가 잘못되었을 수 있습니까?

2013-03-31 reish

'n * (n-1)/2 = 8 * 7/2 = 28'이다. 'n * (n-1)/2'는 여전히 O (n^2)입니다. – nneonneo

@darwish 잘 생긴 아바타) –

더 큰 입력 (예 : 10^5 요소)을 취하면 O (n^2)임을 즉시 알 수 있습니다. –

모든 반복에서 피벗이 이동되어 더 이상 계산되지 않기 때문에 목록이 하나의 요소만큼 축소됩니다. 따라서 총 반복 횟수는 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28입니다.

n*(n-1)/2과 같기 때문에 여전히 2 차입니다.

2013-03-31 10:07:07 nneonneo

n = 8의 경우 반복 횟수는 28 회입니다.

반복의 수가 동일하다 n*(n-1)/2 = 8 * 지금 = 28

함수 F (N) = N이다 * 7/2 (N-1)/2 = N ²/2 - n/2. = O ((1/2) N 2) = O (n은 2^{) - F (N) = O (N/2 N 2 /2) 거기}

.

따라서 귀하의 의견은 사실 Quicksort의 최악의 경우입니다.

2013-03-31 11:20:25 Deepu

답변