[Quick Sort] Quick sort는 왜 빠를까? (2) : 기대값을 고려한 Quick sort / Quick sort의 Expected running time /
Expected Running Time이란? 만약 동전을 100번 던진다고 치자. 우리는 앞면이 최대 100번 나올 수 있는 것을 당연히 알고 있다. 하지만, 또한 우리는 앞면이 평균 50번 정도가 나올 것도 알고 있다. 50번보다 조금 나올 때도 있을 것이고, 50번보다 많이 나오는 때도 있을 것이지만, 우리는 시행이 거듭될 수록, 50번에 수렴한다는 것을 직감적으로 알고 있다. 이 50이라는 숫자가 이 100번 던지는 시행의 기대값이다. Quick Sort의 경우에도 우리가 정렬을 사용할 때를 적용하려면 최악의 경우가 아닌 이런 기대값 Running Time 이 중요할 것이다! QuickSort 의 Expected Running Time 앞서 말했듯이 input값이 랜덤한 값들로 들어온다고 했을때, ..
2019. 10. 21.
[Quick Sort] Quick sort는 왜 빠를까? (1) : Randomized 된 Quicksort / Quick sort의 Worst running time (최악)
Quick Sort란? 피벗을 중심으로 작은쪽, 큰쪽으로 나누어 정렬하는 방식을 뜻한다. 메모리 소비가 없고 무엇보다 정렬속도가 빠르기 때문에 Quick sort로 이름이 붙여졌다. (* 참고 : https://coderkoo.tistory.com/7) Quick Sort의 시간복잡도 허나 다들 알다시피 Quick Sort의 시간복잡도는 O(n^2) ,Ω(n lgn) 이다. (이는 구글에 검색해보면 자료가 많으니 생략, 아까 링크한 블로그에 자세히 설명이 되어있다!) 최악과 최적 모두 Θ(n lgn) 인 Heap Sort와 Merge Sort 에 비하면 겉보기에는 느릴 수 있어보인다. 그렇다면 왜 Quick Sort는 Quick Sort 인 것일까? Randomized 된 Quicksort의 최악은? 우..
2019. 10. 21.
[Quick Sort] Quick sort는 왜 빠를까? (2) : 기대값을 고려한 Quick sort / Quick sort의 Expected running time /
Expected Running Time이란? 만약 동전을 100번 던진다고 치자. 우리는 앞면이 최대 100번 나올 수 있는 것을 당연히 알고 있다. 하지만, 또한 우리는 앞면이 평균 50번 정도가 나올 것도 알고 있다. 50번보다 조금 나올 때도 있을 것이고, 50번보다 많이 나오는 때도 있을 것이지만, 우리는 시행이 거듭될 수록, 50번에 수렴한다는 것을 직감적으로 알고 있다. 이 50이라는 숫자가 이 100번 던지는 시행의 기대값이다. Quick Sort의 경우에도 우리가 정렬을 사용할 때를 적용하려면 최악의 경우가 아닌 이런 기대값 Running Time 이 중요할 것이다! QuickSort 의 Expected Running Time 앞서 말했듯이 input값이 랜덤한 값들로 들어온다고 했을때, ..
[Quick Sort] Quick sort는 왜 빠를까? (1) : Randomized 된 Quicksort / Quick sort의 Worst running time (최악)
Quick Sort란? 피벗을 중심으로 작은쪽, 큰쪽으로 나누어 정렬하는 방식을 뜻한다. 메모리 소비가 없고 무엇보다 정렬속도가 빠르기 때문에 Quick sort로 이름이 붙여졌다. (* 참고 : https://coderkoo.tistory.com/7) Quick Sort의 시간복잡도 허나 다들 알다시피 Quick Sort의 시간복잡도는 O(n^2) ,Ω(n lgn) 이다. (이는 구글에 검색해보면 자료가 많으니 생략, 아까 링크한 블로그에 자세히 설명이 되어있다!) 최악과 최적 모두 Θ(n lgn) 인 Heap Sort와 Merge Sort 에 비하면 겉보기에는 느릴 수 있어보인다. 그렇다면 왜 Quick Sort는 Quick Sort 인 것일까? Randomized 된 Quicksort의 최악은? 우..