Computer Science/Algorithm

[Algorithm] 시간 복잡도(time complexity)와 알고리즘 수행 시간

ooeunz 2019. 10. 24. 16:03
반응형

Code Force

빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 바로 알고리즘의 속도를 측정하는 것이다. 이러한 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것일 것이다. 하지만 이러한 방법은 일반적인 기준이 되기에는 부적합하다. 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있기 때문이다. 그렇다면 알고리즘의 수행 시간을 어떤 기준으로 측정해야 할까?

 

반복문이 알고리즘 수행 시간을 지배한다.

한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다(dominate)라고 표현한다. 알고리즘에서 이러한 역할을 하는 것이 바로 반복문이다. 물론 입력에 상관 없이 항상 같은 수행 시간을 갖는 알고리즘도 있지만, 대개는 입력의 크기에 따라 수행 횟수가 있기 마련이다. 반복문은 입력의 크기가 커지면 커질수록 알고리즘의 수행 시간을 지배하게 된다. 때문에 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다. (이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현)

 


시간 복잡도

시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이다. 즉 시간 복잡도가 낮다고 해서 언제나 빠르게 동작하는 것은 아니라는 말이다. 시간 복잡도가 낮은 알고리즘은 입력이 커질수록 더 효율적이게 된다.

시간 복잡도를 측정하는 방법 최선의 수행시간, 평균적인 수행 시간, 최악의 수행 시간으로 나눌 수 있다. 이 세 개의 기준 중 사람들은 대개 최악의 수행 시간을 사용한다.

 

 

빅 오 표기법(Big-O Notation)

알고리즘이 복잡할 때 코드를 한 줄 한 줄 읽으면서 복잡도를 계산하는 것은 정신 건강에 좋지 못하다. 때문에, 빅 오 표기법에서는 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 된다. 즉 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다. O 표기법은 각 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련 있는 것은 아니기 때문에 착각하지 않도록 주의해야 한다.

 

  • O(N) : 입력한 크기에 비례하는 알고리즘.
  • O(logN) : 연산 할 때마다 연산해야 할 횟수가 1/2로 줄어듦. (N을 계속 절반으로 나눠서 1 이하가 될 때까지 몇 번이나 나눠야 하는지)
  • O(N^2) : 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있음.
  • O(2^N) : 모든 답 후보를 평가하는 경우임. (Brute Force : 이 알고리즘은 무식하지만, 이 보다 빠른 알고리즘을 찾지 못한 문제가 전산학에 쌓이고 쌓였다.)

 

 

수행 시간 어림짐작하기

실제 대회나 코딩 테스트 상황에서는 시간 제한을 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 한다. 때문에 어떤 알고리즘이 이 문제를 해결할 수 있을지 알기 위해서는 프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 한다.

 

예를 들어 입력의 최대 크기 N이 10000이고, 시간제한이 1초인 문제를 풀고 있다면, 입력의 크기를 우리가 만들어낸 알고리즘의 시간 복잡도에 대입해서 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간제한을 초과할 가능성이 있는 것이다.

 

하지만 앞에서도 이야기 했듯이, O 표기법은 최악의 수행 시간과 관련 있는 것이 아니다. 때문에 우리가 어림짐작으로 수행 시간을 짐작해보더라도 아래의 이유로 인해서 우리의 예상 수행 속도에 미치지 못할 수도 있다.

 

  1. O 표기법은 시간 복잡도를 표현할 때 상수나 최고차항 이외의 항들을 모두 제외하기 때문에 실제 결과는 차이 날 수 있다.
  2. 반복문의 내부에 시간이 많이 걸리는 연산이 있을 경우 가정보다 시간이 오래 걸릴 수 밖에 없다.
  3. CPU는 메모리에서 캐시로 데이터를 불러온 뒤 처리한다. 만약 메모리 주소 상 인접한 데이터를 가져올 때는 매번 메모리에 접근할 필요 없이 캐시에 있는 데이터를 사용하게 된다. 그런데 메모리 사용 패턴이 복잡할 경우 매번 메모리에 접근해야 하기 때문에 실제 수행 속도에서 차이가 날 수 있다.
  4. 언어와 컴파일러 차이
  5. 구형 컴퓨터를 사용하는 경우

 

때문에 이러한 수행 시간 어림 짐작은 실제와 차이가 있을 수 있으므로 충분한 여유를 두는 것이 좋다. 쉬운 일은 아니지만, 작성하는 프로그램들의 시간 복잡도와 수행 시간의 상관관계에 대한 경험과 인사이트가 있다면 큰 도움이 된다.

반응형