그러면 10 개의 문자열을 입력하면이 두 가지 종류에 대해 최상의 또는 최악의 경우를 얻을 수 있도록 어떻게 입력 할 수 있습니까?
Heap sort: best case - nlogn worst case - nlogn Quick sort: best case - nlogn worst case - n^2 이 두 가지를 혼동하는 부분은 다음과 같습니다.
- 힙 -최상의 경우와 최악의 경우가 동일하기 때문에 입력 순서가 중요하지 않습니까? 비교 및 할당 수는 항상 동일합니까? 힙 정렬에서 실제 작업이 삽입에서 수행되기 때문에 동일 할 수 있다고 상상하지만 정렬은 최대 / 최소 힙 제거 만 사용합니까? 그게 이유인가요?
- 빠른 정렬 -이건 확실하지 않습니다. 이에 대한 최선의 상황과 최악의 상황이 무엇인지 확실하지 않습니다. 예를 들어 이미 정렬 된 10 개의 문자열 목록이 “재귀 알고리즘을 완성하기 위해 항상 같은 양의 피벗을 선택해야하는 것은 아닙니다.이 설명에 대한 도움이 정말 도움이 될 것입니다.
댓글
- Quicksort는 종종 무작위 알고리즘으로 구현된다는 사실을 알아야합니다.이 사실을 모르는 것 같습니다.
- $ n \ log n $와 $ O (n \ log n) $의 차이를 알고 있어야합니다. Landau 표기법 을 참조하세요.
답변
heap- 최상의 경우와 최악의 경우가 동일하므로 입력 순서는 중요하지 않습니까? 비교 및 할당의 수는 항상 동일합니까? 힙 정렬에서는 실제 작업이 삽입에서 수행되기 때문에 동일 할 수 있다고 상상하지만 정렬은 제거 만 사용합니다. 최대 / 최소 힙입니까? 그 이유가 무엇입니까?
실제 비교 횟수는 값이 제공되는 순서. 최선과 최악의 경우가 각각 Θ (n log n)이라는 사실 (모든 요소가 구별된다고 가정)은 점근 적으로 차이가 없음을 의미합니다. 둘 사이에는 일정한 요인에 따라 다를 수 있습니다. 제 머릿속에 이것에 대한 간단한 예는 없지만 비교 횟수가 일정한 요인에 의해 다른 입력을 구성 할 수 있다고 생각합니다. 두 가지 접근 방식. 그러나 big-O 표기법은 상수를 무시하기 때문에 “최상의 경우 및 최악의 경우 분석에 반영되지 않습니다.
빠른 정렬-이것은 나는 확실히 모른다. 예를 들어 10 개의 문자열로 구성된 이미 정렬 된 목록이 있다면 재귀 알고리즘을 완성하기 위해 항상 같은 양의 피벗을 선택해야하지 않겠습니까? 이 설명에 대한 모든 도움이 정말 도움이 될 것입니다.
선택한 피벗 수는 알고리즘 실행에 관계없이 실제로 동일합니다. 그러나 피벗 당 수행되는 작업 은 수행하는 분할 유형에 따라 달라질 수 있습니다. 최상의 경우 각 단계에서 선택한 피벗은 배열의 중앙값이됩니다. 이런 일이 발생하면 재귀의 최상위 계층에서 (대략) n 개의 비교가 수행되고 다음 계층에서 (대략) n 크기가 n / 2 인 두 개의 하위 배열이 있기 때문에 다음 계층에 (대략) n이 있습니다. 크기 n / 4 등의 네 개의 하위 배열이 있기 때문입니다. Θ (log n) 레이어가 있고 각 레이어가 Θ를 수행하기 때문입니다. (n) 작업, 수행 된 총 작업은 Θ (n log n)입니다. 반면에 각 어레이의 절대 최소값을 피벗으로 선택하는 것이 좋습니다. 그런 다음 (대략) n 개의 비교가 최상위 계층에서 수행되고 (대략) n-1이 다음 계층에서 수행되고 (대략) n-2가 다음 계층에서 수행됩니다. 합계 1 + 2 + 3 + … + n은 Θ (n 2 )이므로 최악의 경우입니다.
도움이되기를 바랍니다!
댓글
- 선생님, heapsort nlogn의 최상의 사례는 무엇입니까? 모든 요소가 동일하다고 생각하면 비용은 배열의 모든 요소를 반복하고 루트까지 이동하지 않습니다. 그래서 저에 따르면 오메가 (n)이어야합니다.
- 좋은 지적입니다. 고유 한 요소를 가정 했으므로이 답변을 업데이트하겠습니다.
답변
아무도 실제로 heapSort를 해결했습니다 :
배열로 표현 된 최대 힙을 사용하고 최대 요소를 출력 배열에 거꾸로 삽입하거나 배열의 뒷면에 삽입한다고 가정합니다. , heapSort에 대한 최악의 경우 입력은 요소를 제거 할 때마다 “버블 다운”하거나 재충전해야하는 입력입니다. 이는 중복이없는 집합을 정렬하려고 할 때마다 발생합니다. 여전히 Θ (n log입니다. n), templatetypedef가 말했듯이.
이 속성은 heapSort의 최상의 경우는 모든 요소가 같을 때 (Θ (n)입니다. 제거 할 때마다 다시 힙할 필요가 없기 때문에 힙의 최대 높이는 log (n))입니다. 그것은 형편없고 비현실적인 경우입니다. 그래서 heapsort의 실제 최상의 경우는 Θ (n log n)입니다.
댓글
- 비현실적인 사례에 대한 귀하의 요점은 제 알고리즘 수업에서 방금 질문했습니다. (트릭 질문에주의하십시오.) 물론 저는 ' 당신의 요점에 여전히 동의합니다. ( 결과적으로 내 대답이 잘못되었습니다. XD)
답변
-
빠른 정렬
최악의 경우 : $ \ mathcal {O} (n ^ 2) $ . 피벗 요소가 항상 맨 오른쪽 요소라고 가정합니다. $ n $ 요소가있는 정렬 된 목록. 따라서 각 분할은 $ n-1 $ 요소가있는 하나의 목록으로 이어집니다. $ 0 $ 요소가있는 목록 하나입니다. 피벗 요소를 무작위로 선택하더라도 , 여전히 운이 좋지 않을 수 있으며 항상 목록에서 최대 값을 선택합니다.
$ T (n) $ 를 비교 횟수 빠른 정렬로 설정합니다. $ n $ 요소로 목록을 정렬해야합니다. 최악의 경우 : \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ 재귀, $ n $ to partion)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}
최상의 사례 : $ \ mathcal {O} (n \ log n) $ . 피벗 요소가 이러한 방식으로 선택되면 목록을 균등하게 분할합니다.
\ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 x $ \ frac {n} { 2} $ 재귀, $ n $-파티션)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}
-
힙 정렬
힙 정렬의 최악의 경우와 최상의 경우 복잡성은 모두 $ \ mathcal {O} (n \ log n) $입니다. . 따라서 힙 정렬에는 모든 입력 배열에 대해 $ \ mathcal {O} (n \ log n) $ 비교가 필요합니다. 힙 정렬의 복잡성 :
\ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i-\ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {로그 몫 규칙}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }
댓글
- ' t는 OP '의 모든 질문에 답변 했으므로 놓친 질문에 답변하겠습니다. 힙 정렬은 ' 주어진 요소 수에 대해 항상 동일한 수의 비교를 사용하지는 않습니다. 최악의 경우는 $ a \, n \ log n $이고 최상의 경우는 $ b \, n \ log n $입니다. 여기서 $ a > b $
- 또한 3 방향 변형 은 단일 요소 입력에 대한 최적의 선형 사례를 가지고 있습니다.