시간 복잡도
문제 해결에 필요한 입력값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 한다. 그 중 얼마나 오래 걸리는지는 시간 복잡도라고 하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도라고 한다.
빅오(Big-O) 표기법
실제로 코드를 실행해보면 소프트웨어나 하드웨어적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다르다. 이런 차이 때문에 시간을 정확한 수치로 표현하기는 어렵지만, 문법이나 구성에서 발생하는 비용을 수치화해 문제를 푸는 데 필요한 총 연산의 수를 수학적으로 표기할 수 있다. 이를 점근 표기법이라고 하며, 세 가지 표기법 중 가장 흔하게 사용하며, 최악의 경우를 계산하는 계산법을 빅오(Big-O) 표기법 이라고 한다.
빅오 표기법은 알고리즘이 해당 차수이거나, 그보나 낮은 차수의 시간 복잡도를 가지는 점근적 상한 표기 방법을 의미한다. 쉽게 '최악의 경우 이 정도의 시간이 걸린다'로 이해하면 된다.
수학적으로 정의하면 다음과 같다.
예를 들어 a 변수에 +1 을 하는 코드를 작성했다고 한다면 (코드로 a += 1) 이를 실행하기 위해 필요한 연산은 총 1번이다. 만약 데이터 개수가 n개라면 프로그램을 실행할 때 발생하는 비용을 f(x)라고 가정하면 데이터 개수만큼 연산을 1번 수행하므로 f(n) = n 이라고 표기할 수 있고, 이를 빅오 표기법으로 나타내면 O(n)이 된다.
n개의 데이터를 수행하는 데 걸리는 시간이 제곱만큼, f(n) = 4n^2 + 4n + 1이라고 한다면 동일 최대 차수인 최소 단위 시간 복잡도 g(n) = n^2이 있을 때 f(n) <= cg(n)이 성립하는 상수 c가 존재하므로 결론적으로 표기법 O(x)를 사용하여 최소 단위인 O(n^2)으로 표현할 수 있다.
즉, 연산 횟수가 최고 차항에 비례하는 흐름을 보인다면 부가적인 연산은 신경 쓸 필요가 없다. 가령 n^2 + 2n + 1 의 시간 복잡도 역시 최고 차항만 계산하여 O(n^2)으로 줄어든다. 같은 이유로 99n의 시간 복잡도는 O(n)으로 줄어든다.
시간 복잡도 그래프
각 시간 복잡도에 따른 연산 횟수를 정리하면 다음과 같다.
