O (log n) quicksort 복잡성, 가능합니까?

Question

퀵 정렬의 pivot_value 복잡성의 특정 값에서 로그가 발생 할 수 있습니까?

Answer 1

번호

매우 첫 번째 파티션에 관계없이 당신이 선택 피벗 값에 O(n) 시간이 걸릴 것입니다 - 당신은 피벗에 다른 모든 요소를 ​​비교해야합니다.

다음은 두 파티션 모두에 대해 동일하게 반복 실행합니다. 피벗의 최적 선택 (각 피벗이 범위의 중앙값 일 때)은 O(n log n)의 복잡도로 끝납니다. 피벗의 최악의 선택 (각 피벗이 범위에서 가장 크거나 작은 값일 때)은 O(n^2)의 복잡도로 끝납니다.

Answer 2

아니요. 복잡성의 개념은 사적인 사례에서 분리됩니다. 전체적인 내용입니다. 비교 작전 (빠른 종류가 같은 알고리즘)을 사용하여 정렬

Answer 3

번호

는 Omega(nlogn) 연산을 입증한다 - 따라서 그것은 O(nlogn)보다 더 나은와의 definetly하지 O(logn)

---

에서 수행 할 수 없습니다

데이터를 조작하기 위해 가능한 결과가 2/3 인 연산자를 사용해야하므로 비교를 사용하여 정렬은 Omega(nlogn)입니다. 거기 엔 n! 데이터에 대한 순열, 당신이 Omega(log(n!))이 작전을 비교하고, 엄격하게 nlog(n)에 의해 묶여있다 (! n)에 로그인해야합니다 의미 - 그래서 정렬은 빠른 정렬에 의해 Theta(n)최상의 경우에서 수행 될 수 있음을 Omega(nlog(n))

---

주입니다 목록이 정렬되어 있는지 확인하고 그럴 경우 중단하지만이 경우를 이길 수있는 경우는 없으며 모든 경우에 대해 로그 해밀 복잡성에 도달 할 수 없습니다.

Answer 4

아니요. 정렬 알고리즘이 올바른 알고리즘 (즉, 가능한 모든 입력에 대해 항상 올바른 출력을 생성합니다.)을 위해 Quicksort와 같은 비교 정렬 알고리즘은 적어도 n * log (n) 비교를 수행해야합니다. 그렇지 않으면 올바른 출력을 판별 할 수없는 입력이 있습니다. 이것은 decision tree model에서 가장 쉽게 시각화됩니다. 각 리프는 알고리즘의 올바른 출력에 해당합니다. 유명한 CLRS 교과서 p193에서

는 :

의 도달 잎의 어느 의사 결정 트리의 루트에서 가장 긴 간단한 경로의 길이는 해당 분류 것을 비교 최악의 경우의 수를 나타냅니다

알고리즘이 수행합니다. 결과적으로 주어진 비교 정렬 알고리즘에 대한 최하위 숫자 인 비교는 해당 결정의 높이와 같습니다. 트리. 따라서 각 순열 이 도달 가능한 잎으로 나타나는 모든 결정 트리의 높이에 대한 하한은 모든 비교 정렬 알고리즘의 실행 시간에 대한 하한값입니다.

의사 결정 트리의 높이는 n * log (n)입니다.

Answer 5

정렬 알고리즘은 알고리즘이 입력을 읽어야하기 때문에 Ω (n) 연산보다 적은 수행을 정렬 할 수 있습니다. .알고리즘은 다음 은 우리가 변경할 수있는 결과, 알고리즘의 실행 을 초래하지 않고 입력의 부분을 변경할 수있는 입력의 일부를 판독하지 않는 경우

: 여기 대적 인수를 사용 LOWERBOUND 인 대답은 알고리즘은이 부분을 읽지 않으므로이 변경 사항을 인식하지 못합니다.

그러나 quicksort는이 하향 연결을 수행하지 않습니다. 비교 기반 알고리즘은 최악의 경우 (또는 평균 경우) 실행 시간 O (n)을 가질 수 없습니다. 모두 Ω (n lg n) 비교 연산이 필요합니다. 결정 트리 lowerbound 인수를 사용하여 표시 할 수 있습니다.

QuickSort 알고리즘 의 가장 복잡한 경우 (피벗이 최적으로 선택되었음을 의미 함) 은 Dukeling의 설명대로 Ω (nlg n)입니다.

알고리즘을 수정하여 특정 종류의 입력 (이미 정렬 된 배열)에 대한 해답을보다 효율적으로 하드 코딩하고 최상의 실행 시간을 잠재적으로 향상시킬 수 있습니다. 얼마나 효율적인지에 따라 얼마나 빨리 달라지는가 입력이 특수 사례 중 하나에 속하는지 확인할 수 있으며 이러한 특정 사례에 대한 답변을 얼마나 빨리 출력하는지 확인할 수 있습니다. 배열이 이미 정렬되어 선형 시간으로 출력되는지 확인할 수 있습니다. 그래서이 특별한 경우를 하드 코딩하여 O (n) 으로 정렬 알고리즘의 최상의 경우의 복잡성을 개선 할 수 있습니다.