중간 요소를 피벗으로 사용하는 빠른 정렬의 최악의 경우의 상한선은 무엇입니까?

-2

중위 요소 (중앙값이 아닌 중간 요소)를 피벗으로 선택하는 경우 빠른 정렬의 최악의 경우에 가장 엄격한 상한은 무엇입니까?중간 요소를 피벗으로 사용하는 빠른 정렬의 최악의 경우의 상한선은 무엇입니까?

출처

2014-03-03 user2331262

가운데 중간 또는 중간 위치의 항목은 중간입니까? – user2357112

최악의 경우는 항상 정사각형입니다. 중간 요소를 의미하는 경우 중간 요소를 의미하면 더 이상 최악의 경우가 아닙니다. – Leo

중간 위치의 항목이 중간이 아닌 경우 – user2331262

선형 시간 중앙 피벗 선택 (및 @n.m.의 주석)을 사용하는 결정 론적 퀵 소트는 O (n 로그 n) 최악의 경우 성능을가집니다.

http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting

출처

2014-03-03 05:58:37

배열은 항상 ,'== pivot' 및'> pivot'으로 세분 할 수 있습니다. –

"결정 성있는 빠른 정렬에는 항상 O (n^2) 최악의 경우가 있습니다." - 임의성을 사용하는 방법도 있습니다. 생성 할 '임의의'숫자 (즉, PRNG의 시드)를 알지 못하면 최악의 경우를 구성 할 수 없습니다. 무작위성을 사용하는 경우와 같이 최악의 경우로 입력 예제를 언급 한 이유에 대해서는 잘 모르겠지만 중복을 이용하여 잘 알려진 최적화를 사용하는 것은 최악의 경우는 아닙니다. – Dukeling

@ n.m. 네 말이 맞아, 나는이 명백한 트릭을 잊어 버렸다. 선형 시간 중앙 선택 알고리즘을 사용하면 O (n log n)을 얻을 수 있습니다. –

중간 요소는 다음 입력 배열의 중간 최악의 경우에 대한 시간 복잡도가 O(nlogn) 의미하지만 당신은 정렬되지 않은 배열의 중간 요소를 의미한다면 그것은 최악의 경우 O(n^2) 경우 그 때문에 최악의 경우 0 : n-1에서 언밸런스 파티션이 발생할 수 있습니다. 하지만 평균 경우에도 여전히있을 것입니다. O(nlogn)

출처

2014-03-03 06:49:10

빠른 정렬의 최악 사례는 O (n2)입니다. 평균 사례는 O (nlogn)입니다.

O (n2)는 최악의 경우 상한입니다. O (nlogn)는 예상 경우에 대해 엄격한 경계입니다.

출처

2017-11-09 11:09:51 lemonader

중간 요소를 피벗으로 사용하는 빠른 정렬의 최악의 경우의 상한선은 무엇입니까?

답변

관련 문제