빅오 표기법

시간 복잡도 함수

연산의 수행 횟수는 프로그램에 주어지는 입력의 개수 n 에 따라 변하게 된다.

연산의 개수를 입력의 개수 n 의 함수로 나타낸 것을 시간 복잡도 함수 라고 하고 T(n) 이라 표기한다.

big-oh notation

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 말하며 n 에 비례하는 실행시간을 가진다는 의미로 O(n) 이라 표기한다.

예시

1 부터 n 까지의 합을 구하는 문제의 알고리즘을 예로 들어 보면

int sum = 0;
for(int i = 0; i < n; i++){
    sum = sum + i;
}

모든 연산을 정리하였을 때 대입, 덧셈, 비교연산을 모두 합쳐 시간 복잡도 함수는 T(n) = 5n + 3 이 나온다.

n 의 개수가 무수히 많을 경우 최고차항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있으므로 해당 예시의 빅오 표기법은 O(n) 이다.

또 연산의 개수보다는 함수의 증가 추세가 더 중요하다. 시간 복잡도 함수에서 반복문 제어 연산 수 3n + 2 를 무시하더라도 사진처럼 그 차이는 미미해 동일한 복잡도 함수를 얻게 된다.