쿽소트와 머지소트의 최악의 경우 시간복잡도. 둘의 차이점.

퀵소트와 머지소트의 최악의 경우 시간복잡도

• 퀵소트 최악의 경우 O(n제곱)
  • 퀵소트는 Pivot 이 비교할 때마다 끝까지 다 비교하면 n번 비교할테니 높이 n 과 비교 하는 횟수 n 으로 인해 O(n제곱).
• 머지 소트 O(nlogn)
  • 머지 소트는 분할을 전부 한 후, 마지막에 비교하는 것이기에 최악의 경우라도 O(nlogn)
    • 왜냐하면 높이 logN * 전부 비교한다고 해도 kn 이니 logN*N 이 시간 복잡도

퀵소트와 머지소트 차이점

• 차이점은 퀵소트는 메모리를 안쓴다는 거고. 머지 소트는 입력 배열과 동일한 배열이 필요 (메모리 사용)