algorithm2 Quicksort from CTCI 코딩 인터뷰 완전 분석(원제: Cracking the Coding Interview)에 소개된 Quicksort를 다시 한 번 정리 해보려고 한다. 기본적으로 퀵정렬은, 무작위로 한 원소를 정하고(이를 pivot이라 부른다), pivot보다 작은 원소들은 앞쪽에, 큰 원소들은 뒷쪽에 위치시킨다. 실행시간: 평균 O(n logn), 최악 O(n^2).메모리: O(logn)배열 분할(partition)에 사용되는 원소(pivot)가 배열의 중간값(median) 혹은 중간값에 가까운 값이라면 좋은 성능이 나오겠지만, 반드시 그러리라는 보장은 할 수 없다. 즉 퀵정렬은 pivot을 어떻게 정하느냐에 따라 느리게 동작할 수도 있으며, 최악의 경우 수행시간이 O(n^2)이 될 수 있다. 이전에 작성했던 퀵정렬(Ho.. 2019. 3. 2. Big-O Notation (빅오 표기법) 복잡도(Complexity)는 크게, 시간 복잡도 (Time Complexity) 공간 복잡도 (Memory Complexity) 의 2가지로 나눌 수 있는데, 요즘은 메모리 가격이 많이 낮아져서 공간 복잡도보다는 주로 시간 복잡도에 더 관심을 기울이는 편이다. 시간 복잡도란 즉, 어떤 알고리즘을 수행하는 데 얼마나 많은 절차(step)를 거쳐야하는지를 나타낸다. 시간 복잡도의 최선의 경우(best case)와 최악의 경우(worst case)를 생각했을 때, 최선의 경우는 별로 의미가 없다. 알고리즘을 수행할 때 최선의 경우가 발생하는 상황은 실질적으로는 드물기 때문이다. 평균(average case)도 생각해볼 수는 있겠지만 최악의 경우에 대한 유의미한 정보를 제공해주지는 않는다. 따라서 알고리즘 간.. 2018. 3. 4. 이전 1 다음