Topic 39 알고리즘의 속도
데이비드 토머스, 앤드류 헌트
느낌표 ! (인상 깊은 문장 | 문맥)
대문자 O 표기법
어떤 정렬 루틴이 원소 n개를 정렬하는 데 O(n) 시간이 걸린다고 말할 떄, 이는 그저 최악의 경우의 걸리는 시간이 n의 제곱에 비례하여 늘어난다고 얘기하는 것이다.
p.292
책에서는 대문자 $O$ 표기법으로 표현하지만 실제로는 빅 오 표기법(big-O notation)으로 더 많이 불리는 것 같다. 빅 오 표기법은 가장 큰 차수를 가지고 표현한다. 예를 들어 $n^2 + 2$ 일 경우 +2 부분은 제외하고 O($n^2$) 로 표현한다.
대문자 O 표기법은 수행 시간이든 메모리든, 아니면 다른 무엇을 나타내든 실제 숫자를 알려주지 않는다. 그저 입력의 크기가 바뀜에 따라 이 값이 어떻게 바뀔지를 알려줄 뿐이다.
p.293
알고리즘을 평가할 때 메모리 사용량과 처리 속도가 중요한데 이 알고리즘이 감당해야하는 최대 데이터 값도 매우 중요하다.
$O(1)$ 상수. (배열의 원소 접근, 단순 명령문)
$O(\lg n)$ 로그. (이진 검색) 로그의 밑은 중요치 않다. 따라서 $O(\log n)$과 동일하다
$O(n)$ 선형. (순차 검색)
$O(n \lg n)$ 선형보다는 좋지 않지만, 그래도 그렇게 많이 나쁘지는 않음. (퀵 정렬과 힙 정렬의 평균 수행 시간)
$O(n^2)$ 제곱. (선택 정렬과 삽입 정렬)
$O(n^3)$ 세제곱. (두 n x n 행렬의 곱)
$O(C^m)$ 지수. (여행하는 외판원 문제, 집합 분할 문제)
p.294
$O(n^2)$ 알고리즘은 최대한 피하려 최대한 의식해야한다.
실전에서의 알고리즘 속도
$O(n^2)$ 알고리즘이 있다면 분할 정복을 사용하여 $O(n \lg n)$ 으로 줄일 수 없는지 시도해 보라.
p.296
이런 경험을 해보고 싶지만 아직 마주쳐보지 못했다.. 빨리 경험해보고 싶은 부분이다. 그리고 가장 약점이라고도 생각이 된다.
어떤 일을 하는 코드인지 코드 자체에 대해서도 생각해 보라. 입력값이 n이 작을 경우, 단순한 $O(n^2)$ 코드가 복잡한 $O(n \lg n)$ 코드보다 더 좋은 성능을 내기도 한다.
p.297
알고리즘이 비효율적이라고해도 데이터 입력 값에 따라 사용 가능 여부는 달라진다. 물론 알고리즘의 퍼포먼스가 좋으면 안 좋을 것 없지만 더 노력이 들어가야하는 곳에 들어가야하기 때문에 꼭 필요한지 고려해봐야한다.
여러분의 추정을 테스트하라.
p.297
빅 오 표기법으로 계산하고 메모리 사용량을 계산하고 끝나는 것이 아니라 실제로 테스트를 해보는 과정 또한 매우 필요하다. 이 부분에 대해서 목소리가 작아지는 것은 큰 이슈는 겪어보지 못했다.
최고라고 언제나 최고는 아니다
그리고 ‘성급한 최적화 premature optimization ‘를 조심하라. 언제나 어떤 알고리즘을 개선하느라 여러분의 귀중한 시간을 투자하기 전에 그 알고리즘이 정말로 병목인지 먼저 확인하는 것이 좋다.
p.298
필자는 지금도 완벽주의자에서 완전 벗어나지 못해 때로 스스로 옭아매지는데 정말 때로는 넘어갈 필요도 있고 너무 많은 고민이 필요없을 경우가 더 많다. 물론 고민하기 때문에 더 많은 이해와 깊이가 생기는 것은 사실이지만, 그것이 필요한지는 항상 판단해야한다.
Topic 39 느낌
Topic 39 에서는 알고리즘 평가를 위한 기본적인 설명을 하고 있다.