QuickSort가 n log n 인 이유에 대한 직관적 인 설명?

Question

누구나 '평범한 영어'를 제공 할 수 있습니까? QuickSort n log n을 만드는 것이 직관적이면서도 공식적인 설명입니까? 내 이해에서 그것은 n 항목을 통과해야하며,이 로그를 n 번 수행합니다 ...이 로그를 n 번 수행하는 이유를 단어에 넣는 방법을 모르겠습니다.

Answer 1

각 분할 작업에는 O (n) 작업 (배열에서 한 번만 수행)이 필요합니다. 평균적으로 각 분할은 배열을 두 부분으로 나눕니다 (로그 연산까지 합계 함). 전체적으로 O (n * log n) 연산이 있습니다.

e.e. 평균 log n 파티셔닝 작업에서 각 파티셔닝은 O (n) 작업을 필요로합니다.

Answer 2

log n 부분은 (적어도 이상적으로) 매 반복마다 입력을 절반으로 나누었 기 때문입니다. N 개의 항목부터 시작하여 매번 절반으로 나누면 로그 (N) 회 반복 후 항목 1 개까지 내려 갔다는 것을 의미합니다.이 시점에서 분명히 더 이상 세분화 할 수 없습니다. 예를 들어 128 개의 항목부터 시작하여 64, 32, 16, 8, 4, 2, 1 항목 - 반복 7 개 그룹으로 나눕니다 (로그 (128) = 7).

각 반복은 전체 배열을 스캔하여 파티션을 분할하므로 전체 복잡도가 O (n log n) 인 경우 O (n) 개의 복잡도를 갖는 O (로그 N) 연산으로 끝납니다.

기술적으로 올바른 Big-O는 O (N)입니다. 이는 파티션 요소를 충분히 잘못 선택하면 어레이를 한쪽 요소의 한 요소로, 나머지 배열 전체를 다른 요소로 분할 할 수 있기 때문에 발생합니다. 이 작업이 매 반복마다 발생하면 N 개의 반복 작업을 통해 하나의 요소 조각으로 나눕니다. 그러면 O (N * N) 전체에 대해 N 개의 연산이 O (N)의 복잡성을 갖습니다.

실제 구현에서는 일반적으로 그 전에 멈추지 만 가장 멀리 갈 수 있습니다.

Answer 3

음, 항상 n (log n)이 아닙니다. 선택한 피벗이 대략 중간에있는 것은 연주 시간입니다. 최악의 경우, 가장 작은 요소 또는 가장 큰 요소를 피벗으로 선택하면 시간은 O (n^2)가됩니다.

'n log n'을 시각화하려면 피벗을 정렬 할 배열의 모든 요소 평균에 가장 가까운 요소로 가정 할 수 있습니다. 이렇게하면 어레이가 거의 동일한 길이의 두 부분으로 분할됩니다. 둘 다 quicksort 절차를 적용합니다.

각 단계에서 배열의 길이를 반으로 줄이면 length = 1에 도달 할 때까지 log n (기본 2) 시간 동안 수행됩니다. 즉 정렬 된 배열은 1 요소입니다.

Answer 4

실제로 모든 N 요소 (피벗)의 위치를 ​​찾아야하지만 각 요소에 대한 최대 비교 횟수는 logN입니다. 첫 번째 요소는 N이고 두 번째 요소는 N/2,3rd N/4입니다. . 피어싱 피벗은 중간 요소입니다.