[알고리즘] 시간 복잡도(Time Complexity)와 Big-O 표기법

알고리즘에서 실행시간은 실행환경에 따라 달라진다. 같은 알고리즘이어도 하드웨어, 운영체제, 언어, 컴파일러... 등의 환경에 따라 실행되는 시간은 달라질 수 있기 때문에 이를 절대적인 시간 단위(1초, 2초)로 말할 수 없다.

그래서 실행시간을 측정하는 대신에, 알고리즘 코드의 효율성을 알기 위해 연산의 실행 횟수를 카운트하는 방식이 채택된다.

점근적(Asymptotic) 분석

---

알고리즘의 시간 복잡도를 나타낼때는 점근적 표기법을 사용한다. 데이터의 개수가 n에서부터 무한대로 증가할 때, 수행시간의 증가량을 시간 복잡도로 표현하는 기법이다. 대표적인 예로 Big-O 표기법이 있다. Big-O 표기법은 n값의 변화에 따른 최악의 경우의 시간 복잡도를 고려한다.

Big-O를 사용한 점근적 시간 복잡도 표기법에는 $O(1), O(n), O(log n), O(n^2), O(2^n)...$ 시간이 있다.

1. O(1)

int fun(int data[], int n)
{
	int k = n/2;
    return data[k];
}

n에 관계 없이 상수 시간이 소요되므로 위 코드의 점근적 시간복잡도는 O(1)이다. 일반적으로 n에 따른 반복문이 없는 경우에는 n의 값이 증가하더라도 코드의 실행 시간이 변화하지 않기 때문에 상수 시간인 O(1)을 가진다.

이 때 코드가 2줄 실행되므로 O(2)가 아닌가 하는 의문을 가질 수 있는데, 말 그대로 점근적 표기법이기 때문에 상수 시간이 소요되는 코드는 점근적으로 O(1)로 표현한다.

2. O(n)

int sum(int data[], int n)
{
	int sum = 0;
    for(int i = 0; i < n; i++)
    	sum = sum + data[i];
    return sum;
}

위 코드에서 가장 자주 실행되는 문장은 0부터 n까지의 for 반복문이며, 실행 횟수는 항상 n번이다. 가장 자주 실행되는 문장의 실행 횟수가 n번이라면 다른 연산들의 실행 횟수의 합도 n에 선형적으로 비례하게 된다. 이를 선형 시간복잡도를 가진다고 하고 O(n)이라고 표기한다.

3. O(log n)

double fun(int n) {
	double sum = 0;
    for(double i = 1.0; i < n; i *= 1.5)
    	sum += i;
    return sum;
}

for문에서 n의 값이 증가할 때마다 i의 값은 1.5배씩 증가한다. 언뜻 보면 O(n)과 비슷해 보이나, n값의 증가를 그래프로 그려보면 로그함수의 형태를 띈다. 이를 로그 복잡도를 가진다고 하며 시간 복잡도는 O(log n)으로 나타낸다.

4. O(n^2)

int fun(int n) {
	for(int i = 0; i < n; i++)
    	for(int j = 0; j < n; j++)
        	// do something
    return n;
}

알고리즘이 n번의 실행횟수를 가질 때 시간복잡도는 O(n)을 갖는다고 한다. 그리고 위와 같은 이중 for문을 가지는 코드의 실행횟수는 n*n, 즉 n^2이다. 따라서 알고리즘의 시간 복잡도는 O(n^2)로 나타낸다.

• 위는 n의 값에 따른 Big-O 표기법의 시간복잡도 그래프이다. 그래프를 보면 상수 시간에 가까운 시간 복잡도들은 n이 증가하더라도 시간 증가량의 폭이 크지 않다. 반면에 O(n!)에 가까울수록 n의 증가에 따른 시간 증가량이 대폭적으로 증가한다.

알고리즘의 목표는 코드를 최적화하는 것이라고 할 수 있다. 브루트 포스(완전 탐색)로 풀면 쉽게 풀 수 있는 문제를 프로그래머들은 온갖 방법을 통해 최적화하여 실행 시간을 최대한 단축시키려고 노력한다. 알고리즘의 이해는 시간 복잡도의 이해에서부터 시작되고, 내 코드에 컴퓨터가 얼마나 많은 연산을 하는지 직관적으로 이해할 수 있게 되는 것이 중요하다.

참고자료
시간복잡도와 점근적 분석 / https://youtu.be/kg-bcK1ygIA