알고리즘의 시간 복잡도 분석 (1) - 시간 복잡도와 수행 시간

이 포스팅은 알고리즘 문제 해결 전략 책을 공부한 후 작성한 것입니다.

알고리즘의 속도 측정

• 알고리즘의 속도를 프로그램의 수행 시간으로 측정하는 방법은 가장 직관적
• 그러나 일반적인 기준에는 부적합
  • 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 수많은 요소에 의해 바뀔 수 있기 때문
  • 이런 요소를 모두 통제해도 문자열 구현, 함수 인자 전달 방식 등에 의해 최종 수행 시간의 편차는 커질 수 있음
  • 프로그램의 실제 수행 시간이 입력의 크기나 특성에 따라 달라질 수 있음
• 알고리즘의 수행 시간은 반복문이 지배
  • 지배한다(dominate): 한 가지 항목이 전체의 대소를 좌지우지하는 것
  • 입력의 크기가 커지면 커질수록 반복문이 알고리즘의 수행 시간을 지배함
  • 따라서 보통 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정
    • 예를 들어, N의 크기를 갖는 배열을 이중 반복시키면 그 알고리즘의 수행 시간은 N^2

시간 알고리즘의 종류

선형 시간 알고리즘

• 입력의 크기 N에 대비해 걸리는 시간을 그래프로 그렸을 때 직선이 되는 알고리즘
• 중복된 계산을 제거하면 속도가 향상됨

선형 이하 시간 알고리즘

• 입력의 크기 N이 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘
• 그래프로 표현하면 로그 형태

지수 시간 알고리즘

• N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘
• 가능한 답의 수를 한 번씩 다 확인하기 때문에, 전체 수행 시간은 만들 수 있는 답의 수에 비례

다항 시간 알고리즘

• 반복문의 수행 횟수를 입력 크기의 다항식(N의 거듭제곱들의 선형 결합으로 이루어진 식)으로 표현할 수 있는 알고리즘
• 다항 시간 분류에 포함되는 알고리즘 간에는 엄청나게 큰 시간 차이가 존재할 수 있음 (N^2, N^50, N^100 모두 다항 시간이기 때문)

상수 시간 알고리즘

• 입력의 크기와 상관없이 항상 같은 시간이 걸리는 알고리즘

시간 복잡도 (time complexity)

• 가장 널리 사용되는 알고리즘의 수행 시간 기준
• 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
  • 기본적인 연산: 더 작게 쪼갤 수 없는 최소 크기의 연산
    • 예시: 사칙연산, 대소 비교, 변수 할당 등
    • 반례: 배열 정렬, 문자열 일치 확인, 소인수 분해 등
• 가장 깊이 중첩된 반복문의 수행 횟수를 계산하는 것이 시간 복잡도의 대략적인 기준이 됨
  • 보통 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 때문
  • 물론 기본적 연산이 하나 이상일 수도 있지만 시간 복잡도 계산에서는 대개 상수를 무시하기 때문에 큰 영향은 없음
• 시간 복잡도가 높다 = 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다
  • 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아님
  • 입력의 크기가 충분히 작을 경우 시간 복잡도가 높은 알고리즘이 더 빠를 수도 있음
  • 입력의 크기가 낮은 알고리즘은 입력이 커질 수록 효율적
  • 입력의 크기가 매우 작을 경우 시간 복잡도는 큰 의미가 없을 수도 있음

입력의 종류에 따른 수행 시간의 변화

• 입력의 크기 뿐 아니라 형태도 시간 복잡도에 영향을 미침 (원소의 위치 등)
• 크게 최선의 수행 시간, 최악의 수행 시간, 평균적인 경우의 수행 시간(수행 시간의 기대치) 세 가지를 계산해서 사용
• 예시: 선형 탐색 알고리즘

def firstIndex(array, element):
    for i in range(len(array)):
        if array[i] == element:
            return i
    return -1

• 이 세 개의 기준 중 사람들이 대개 많이 사용하는 것은 최악의 수행 시간 혹은 수행 시간의 기대치
  • 여러 알고리즘에서 이 기준이 거의 같기 때문 (모든 알고리즘이 같은 것은 아님)

▶ 2편 알고리즘의 시간 복잡도 분석 (2) - 빅오표기법 (Big-O Notation) 바로 가기