이 부분은 <Think Complexity>(O’Reilly, 2012)을 발췌 편집한 것이다. 이 책을 끝냈을 때 <Think Complexity>로 넘어갈 수도 있다. 알고리즘 분석은 알고리즘의 수행 성능, 특히 실행시간 복잡도와 공간 요구 사항을 연구하는 컴퓨터 과학의 한 분야다. 알고리즘 분석(https://ko.wikipedia.org/wiki/알고리즘_분석)을 참고하자.
알고리즘 분석의 실질적인 목표는 다양한 알고리즘의 성능을 예측하는 것으로 디자인 결정을 가이드하는 데 있다.
2008년 미국 대선 캠페인에서 버락 오바마 후보가 구글을 방문했을 때 즉흥적으로 분석을 요청받았다. 구글 CEO 에릭 슈미트는 “32비트 정수 백만 개를 정렬하는 가장 효율적인 방법”에 대해 농담으로 물었다. 오바마는 보란 듯이 “버블 정렬만큼은 아니라고 생각한다”고 재빨리 응답했다. 영상으로 볼 수 있다(http://bit.ly/1MpIwTf).
이것은 사실이다. 버블 정렬은 개념적으로는 간단하지만, 데이터셋이 커지면 느려진다. 아마도 슈미트가 기대했던 대답은 “기수 정렬(https://ko.wikipedia.org/wiki/기수_정렬)”이었을 것이다.*
* 그러나 만약 인터뷰에서 이런 질문을 받는다면 "정수 백만 개를 정렬하는 가장 빠른 방법은 제가 사용하는 언어에서 제공하는 정렬 함수를 사용하는 것입니다. 언어에서 제공하는 정렬 함수는 대다수 애플리케이션에서 성능을 충분히 발휘할 것입니다. 만약 애플리케이션이 매우 느리다면 어디서 시간을 가장 많이 소비하는지 확인해보기 위해 프로파일러를 사용할 것입니다. 더 빠른 정렬 알고리즘이 성능에 미치는 영향이 크다면 기수 정렬을 잘 구현한 코드부터 살펴볼 것입니다."라고 대답하는 것이 더 낫다고 생각한다.