알고리즘의 성능을 판단하는 척도
알고리즘의 우수함을 가리는 대표적인 기준을 나열해보자면,
- 정확성 (얼마나 정확한가)
- 작업량 (얼마나 적은 연산을 필요로 하는가)
- 메모리 사용량 (얼마나 적은 공간을 필요로 하는가)
- 단순성 (얼마나 단순한가)
- 최적성 (더 이상의 개선할 여지가 없을 만큼 최적화가 잘 되어 있는가)
이렇게 나열할 수 있습니다.
각각의 기준은 이러한 의미를 갖고 있습니다.
- 정확성은 해당 알고리즘이 input data에 대해 필요한 절차를 거쳐 정확히 수행하고 정확한 output을 내는지의 여부를 나타냅니다.
- 작업량은 요구되는 기능을 수행하는데 필요로 하는 작업의 양을 의미합니다.
- 메모리 사용량은 해당 알고리즘이 특정 작업을 수행하는데 필요한 메모리의 양을 나타냅니다.
- 단순성은 말 그대로 얼마나 흐름이 단순한가 를 기준으로 나타냅니다.
- 최적성은 더 이상 개선할 수 없을 정도로 최적화가 되어있는지를 나타내는 척도입니다.
시간복잡도란?
시간복잡도는 위에서 나열한 알고리즘의 우수함을 가리는 5개의 기준 중에서 작업량을 중점으로 다룹니다. 프로그램의 실행시간은 연산의 양과 관련이 크기 때문에 작업량을 기준으로 시간 복잡도를 계산합니다.
알고리즘 수행 시간 분석의 목표는 다음 3가지를 찾는 것을 목표로 합니다.
-
최선의 경우
딱히 필요 없습니다. 마치 로또에 당첨될 것 이라는 기대만 하고 있는 것과 유사하다고 할 수 있습니다. 그리고, 최선의 경우는 많이 찾아오지 않기에 성능을 개선하는 데에는 거의 쓰이지 않습니다. -
평균의 경우
일반적인 상황에서 소요되는 시간을 말합니다. 어떤 경우에는 이보다 더 빠르게, 또 다른 경우에는 더 느리게 동작할 수도 있습니다. -
최악의 경우
어떠한 경우라도 최악의 경우보다 나쁘지 않습니다. 해당 알고리즘은 아무리 느려도 최악의 경우 의 시간을 보장합니다. 알고리즘 문제를 풀 때 에는 TestCase에 최악의 경우를 시험하는 경우가 대부분이고, 그 이유 때문에 문제 풀이를 할 때 최악의 경우를 계산해서 알고리즘을 설계합니다.
참고로,
최선의 경우에는 빅-Ω 표기법(Big-Omega Notation)
평균의 경우에는 빅-Θ 표기법(Big-Theta Notation)
최악의 경우에는 빅-O 표기법(Big-O Notation)
를 사용합니다.
표기법에 대해서는 다음 글에서 설명할 것 입니다.