시간복잡도(Time Complexity)

우리는 알고리즘의 속도를 어떻게 판단할까? 시간으로 판단할까?
그렇다면 상대적으로 처리속도가 느린 프로세서에서 처리가 느리다면?
이러한 기준에 대한 통일을 위해 알고리즘의 속도를 '단계'의 갯수로 판단한다.

이러한 단계에 대한 평가 척도를 시간 복잡도 라고 한다.

즉, '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 대해 얼마만큼의 시간이 걸리느냐' 가 된다.

빅오(Big-O) 표기법

빅 오 표기법은, 알고리즘의 최악의 경우를 가정한 시간복잡도 표기 기법이다. 예시로 이해해보자. 다음은 배열의 모든 수를 출력하는 C코드 이다.

#include<stdio.h>

int main() {
	int array[] = {1,2,3,4,5,6,7,8,9,10}
    
    for(int i; i < sizeof(array)/sizeof(int); i++) {
		printf("%d",array[i]);
    }
    
    return 0;
}

위 알고리즘을 보면 for문을 이용해 배열의 모든 인덱스에 차레로 접근하여 값을 출력한다. 즉 원소의 갯수 만큼의 단계를 거치므로 총 10단계를 거쳐 실행된다.

여기서 만약 원소의 갯수가 100개가 되면? 당연히 100단계가 될 것이다.

즉, 위 배열의 원소가 N개가 되면 단계도 N단계가 된다.

둘은 선형관계를 가지고 있으므로, 빅 오 표기법으로 다음과 같이 표현한다.

O(N)

위를 선형시간 알고리즘(Linear Time Algorithm) 이라고도 부른다.

반대로 무조건 한단계만 거치는 알고리즘을 생각해보자, 간단하게 그저 아무 배열의 1번째 인덱스 값을 읽는 알고리즘은 원소의 갯수가 1000개든 100개든 단 한단계 만을 거친다. 빅 오 표기법으로 다음과 같이 표현한다.

O(1)

위를 상수시간 알고리즘(Constant Time Algorithm) 이라고도 부른다.

이러한 표기법을 빅 오 표기법이라고 하고, 빅 오 표기법 외에도 두가지 표기법이 더 있다. 빅 오 표기법은 알고리즘의 최악의 상황을 가정한다는 것을 잊지 말자.

아래는 빅 오 표기법 외의 표기법이다.

빅 오메가 표기법

알고리즘의 최상의 상황을 가정한 표기법이다.

빅 세타 표기법

빅 오메가 표기와 빅 오 표기의 평균

다음 글부터는 직접 알고리즘을 작성해보면서 더욱 심화된 과정을 다루도록 하겠다. 이제 알고리즘 공부를 위한 기초적인 개념은 끝났다.