알고리즘의 시간 복잡도 분석

알고리즘을 평가하는 방법

• 시간
  • 알고리즘 수행속도는 굉장히 중요하다.
• 공간
  • 이론적으로 알고리즘이 아무리 빠르더라도 너무 많은 메모리 공간을 요구한다면 수행할 수 없다.

이 두 기준은 서로 상충하는 경우가 많다.

메모리 사용량을 희생해서 속도를 높이거나, 속도를 줄이는 대신 메모리를 아끼는 알고리즘을 자주 볼 수 있다.

도입

알고리즘의 수행시간을 측정하는 기준은 반복문이다.

선형 시간 알고리즘(N)

• 반복문 수행시간이 N일때 이를 선형 시간알고리즘이라 부른다.

선형 이하 시간 알고리즘

이진탐색(logN)

이는 배열이 sort되어 있을 때 사용할 수 있다.

• 구현이 까다로우니 유의하자

다항 시간 알고리즘(N^n + N^(n-1)+ … + N)

우리가 푸는 알고리즘의 대부분의 문제는 이런 알고리즘을 풀게 구현될 수 있다.

지수 시간 알고리즘(2^N)

n이 증가할 수록 시간은 기하급수적으로 증가한다.(다항 시간 알고리즘과는 비교할 수 없을 정도로)

이 알고리즘이 무식해 보이겠지만 이것보다 빠른 알고리즘을 찾지 못한 문제들이 전산학엔 굉장히 많다

지수시간과 다항 시간의 경계는 효율적으로 문제를 해결할 수 있는가를 판단하는 척도이다.

다항 알고리즘이 있는 문제는 계산적으로 쉬운문제, 아직 없는 문제는 계산적으로 어려운 문제라고 이야기한다.