병합 정렬의 복잡성은 모든 경우에 대해() 알고 있지만, 한쪽면에 4 개, 다른면에 5 개가 같은 불균형 인 경우는 예. 9 소자 어레이는불균형 파티션이 병합 정렬의 복잡도에 영향을 미칩니다.
N 개의 퀵 같은 임의의 다른 형태로 로그에서이 변화하는 것처럼 .. 그래서 불균형 N 개의 logn에서 변경 복잡성을 초래하지 ,,, 4 인덱스에서 절단했을 가장 좋은 경우는 nlogn이지만 불균형 피봇 원인은 nlogn에서 n2로 이동합니다.
좋아요. 병합 정렬은 모두 경우에 Θ (n. 로그 n)의 시간 복잡성이 있습니다. 여기에는 해당 크기 'n'이 홀수 인 경우가 포함됩니다.
Big-Oh 표기법에서 시간 복잡성을 고려하면 최종적으로 복잡성을 계산할 때 나타날 수있는 더 낮은 순서의 용어가 항상 제거되기 때문입니다. 'n'이 이상한 경우에는 더 낮은 차수의 용어가 포함되어 있지만 복잡하지는 않습니다. 더 명확히하기 위해 다음 예제를 참조하십시오.
예 : 'n'은 용어의 수이고, 'c'는 나누기 및 병합에 대한 상수 시간입니다. 병합 정렬의 복잡성을 계산에
, 우리가 얻을 :
CN (로그 N + 1). Big-Oh에서 표현할 때 더 낮은 차수의 '+1'과 상수 c는 버려 지므로 Θ (n. log (log n + 1)는 트리의 레벨 수를 나타냄)
엔).
마찬가지로 'n'이 홀수 인 경우이 최종 복잡도에 몇 가지 추가 하위 용어를 사용할 수 있지만 버려지므로 문제가되지 않습니다. 의심 스러워도 복잡성은 증가하지 않습니다. 희망은 분명하다.
더 나은 이해를 얻기 위해이 링크를 참조하시기 바랍니다없는 경우를 많이 나를 helpe ... https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
감사합니다 :) –