D.S.) 알고리즘 성능 분석

성능 분석

문제 해결을 위한 가장 최적의 방법을 택하기 위해서는

각 알고리즘을 분석하고 비교한 후 결정해야한다!

 

그 분석은 일반적으로 공간 복잡도와 시간 복잡도를 통해 수행한다.

 

공간 복잡도

알고리즘을 프로그램으로 실행하여 완료까지 필요한 총 저장공간을 의미한다.

 

시간 복잡도

알고리즘의 프로그램으로 실행하여 완료까지 소요되는 시간을 의미한다.

 

이때, 각 알고리즘을 서로 비교하기 위한 목적이므로

정확한 실행 시간의 측정보다 실행 빈도수를 측정하여 비교한다.

 

일반적으로 알고리즘의 주요 성능 차이는 실행 시간 차이에서 발생하므로

'성능 분석 표기'는 '시간 복잡도 표기'를 의미한다!

빅-오 표기법

알고리즘이 주어졌을 때 최악의 경우를 고려하여 나타내는 표기법이다.

 

출처) Mellon University

위의 그래프를 통해서 

O(1) < O(log n) < O(n) M < O(n log n) < O(n2) < O(2^n) ... 

인 것을 알 수 있다.

 

O(1)

- input의 크기가 소요시간에 영향을 주지 않는 알고리즘

 

O(log n)

ex) i가 n까지 2배씩 증가하는 반복문 or 1/2배씩 감소

 

O(n)

- 반복 횟수가 인풋에 비례한 반복문

ex) for문 안의 for문

 

O(n log n)

- O(n)과 O(n log n)이 함께!

ex) for문 안의 while문 i가 n까지 2배씩 증가