머지소트 퀵소트1 왜 Mergesort 보다 Quicksort를 사용할까? Mergesort가 Quicksort에 비해 항상 유리한 알고리즘이 아닌가? Quicksort에는 최악의 경우 O(n^2)의 시간복잡도를 가지고 있으며, 평균의 경우에는 O(nlogn)의 시간복잡도를 가지고 있습니다. 이에 비해, Mergesort는 최악의 경우와 평균의 경우 모두 O(nlogn)의 시간복잡도를 가지고 있는 굉장히 안정적인 알고리즘입니다. 그래서 알고리즘을 배우면서 Mergesort가 훨씬 유리한 알고리즘 같은데, 왜 Quicksort가 일반적으로 더 많이 사용되는지 알고 싶어졌습니다. 핵심을 말하면, 지역성(Locality) 때문입니다. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. Localit.. 2023. 3. 27. 이전 1 다음
