0. 정리

  • 만약 몇 초만에 실행되어야 하는 프로그램이 몇 시간이 걸린다면, 알고리즘을 최적화 할 게 아니라 더 좋은 알고리즘을 채택해야 한다.

  • 알고리즘의 시간 비용은 $O(f(n))$과 같이 Big-O 표기법으로 나타낼 수 있다.

  • Big-O 표기법은 알고리즘의 실행 시간이 항상 동일하다고 가정하지만, 실제로는 최선의 경우, 최악의 경우, 평균의 경우 시간 비용이 다를 수 있다(Big-Omega 표기법 등이 존재하는 이유이다).

  • Big-O 표기법의 인자에 따라 다음과 같은 의미를 가진다.

    시간 비용 의미
    $O(1)$ 또는 상수 항상 일정한 시간 비용을 갖는다. 보통 가장 빠른 알고리즘이며 누군가 상수 시간 알고리즘을 홍보한다면 의심부터 해 보아야 할 정도이다. 단, 상수 시간 알고리즘이라 하더라도 비례 상수가 매우 크다면 O(N)알고리즘과 다를 바 없어질 수 있다.
    $O(log_2n)$ 선형 시간($n$)보다 작은 시간 비용을 가진다. 입력값이 커지는 속도보다 비용이 증가하는 속도가 느리다. 대표적으로 이진 검색 알고리즘이 있다.
    $O(n)$ 선형 시간을 의미하며, 입력값이 커지는 속도에 비용 증가 속도가 비례해서 증가한다. 일반적으로 프로그램의 입력값이 커지더라도 컴퓨터 자원을 그다지 소비하지 않으나, 선형 시간 알고리즘을 여러 개 결합해서 사용하면 전체 실행 시간이 $O(N^2)$ 이상이 될 수 있다는 점을 유념해야 한다. 따라서 입력값이 커졌을 때 프로그램의 전체 실행 시간이 비약적으로 길어진다면 이 부분을 의심해 봐야 한다.
    $O(nlog_2n)$ 알고리즘의 시간 비용이 선형 시간보다 클 수 있다. 주로 각 단계에서 입력값 쌍을 비교한 후 정렬 공간을 분할하는 알고리즘들이 이 시간 비용을 가진다. 입력값이 증가하는 속도보다 시간 비용이 증가하는 속도가 더 빠르지만, 생각만큼 많이 빠르지는 않으므로 입력값이 크더라도 대체 가능한 수준이다.
    $O(n^2), O(n^3)$ 등 각 입력값을 모든 다른 값들과 비교하는 비효율적인 정렬 알고리즘의 일반적인 속도이다. 이때부터 입력값이 증가하는 속도보다 시간 비용이 증가하는 속도가 매우 빨라지므로 입력값이 크다면 사용을 고려해야 한다.
    $O(2^n)$ 입력값이 증가하는 속도에 비해 시간 비용이 증가하는 속도가 미친듯이 빠르므로, 입력값이 작은 경우에만 사용해야 한다. 대표적으로 외판원 순회TSP, Traveling Salesman Proglem 문제의 시간 비용이 $O(2^n)$이다.

  • 상환 시간 비용amortized time cost은 입력값이 클 때 전체 시간 비용을 입력값으로 나눈 평균 시간 비용을 의미한다.

  • 이진 검색이 가장 빠른 검색 알고리즘은 아니다(보간 검색Interpolation search은 $O(loglogn)$, 해싱은 $O(1)$의 검색 시간을 가진다).

  • 가장 빠른 정렬 알고리즘의 속도를 $O(nlog_2n)$으로 알고 있다면, 잘못 알고 있는 것이다. 입력값의 쌍을 비교하는 정렬 알고리즘만 그러하다. 기수 정렬radix sort의 시간 비용은 $O(nlog_rn)$인데, $r$은 기수 또는 버킷의 개수이다. 또한 플래시 정렬flashsort은 특정 집합에서 키를 가져올 경우 $O(n)$의 시간 비용으로 데이터를 정렬할 수 있다.

  • 삽입 정렬을 비롯한 일부 정렬 알고리즘은 대부분의 데이터가 정렬되어 있을 경우 $O(n)$의 탁월한 성능을 보이며, 빠른 정렬 알고리즘의 대표격인 퀵 정렬은 피벗을 잘못 선정하는 최악의 상황에서 $O(n^2)$의 낮은 효율을 보인다.

  • 대표적인 정렬 알고리즘의 시간 비용은 아래와 같다.

    정렬 최선의 경우 평균의 경우 최악의 경우 필요 공간 비고
    삽입 정렬Insertion sort $n$ $n^2$ $n^2$ 1 정렬되어 있거나 대부분 정렬되어 있을 경우 최선의 경우를 나타낸다
    퀵 정렬Quick sort $nlog_2n$ $nlog_2n$ $n^2$ $log_2n$ 정렬된 데이터일때 처음 또는 마지막 요소를 피벗으로 사용할 경우 최악의 경우를 나타낸다.
    병합 정렬Merge sort $nlog_2n$ $nlog_2n$ $nlog_2n$ 1  
    트리 정렬Tree sort $nlog_2n$ $nlog_2n$ $nlog_2n$ $n$  
    힙 정렬Heap sort $nlog_2n$ $nlog_2n$ $nlog_2n$ 1  
    팀 정렬Tim sort& $n$ $nlog_2n$ $nlog_2n$ $n$ 정렬된 데이터에서 최선의 경우를 나타낸다
    인트로 정렬Intro sort $nlog_2n$ $nlog_2n$ $nlog_2n$ 1  

  • 정렬 알고리즘을 사용할 땐 시간 복잡도와 함께 정렬할 데이터들의 특성을 함께 고려해야 한다. 기존 데이터들이 대부분 잘 정렬된 경우라면 삽입 정렬이나 팀 정렬을 사용하는 것이 유리하다. 반면 데이터 항목이 균등하게 분포되어 있을 때에는 플래시 정렬이 유리하다.

  • 최적화된 코드에는 다음과 같은 반복되는 패턴들이 있다.

    • 사전 계산precomputation
    • 지연 계산
    • 배칭batching
    • 캐싱caching
    • 특수화specialization
    • 더 큰 조각 선택하기
    • 힌팅Hinting
    • 예상 경로 최적화
    • 해싱Hashing
    • 이중 검사double-checking