[Algorithm] 알고리즘 시간복잡도에 대하여

시간복잡도란?

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 있습니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 특히 최근 알고리즘 문제 해결에서 대부분 실행시간을 정해놓고 그 시간안에 소스가 돌아가야 정답으로 체크하기에 시간복잡도의 중요성이 더더욱 커졌다고 볼 수 있습니다.

 

[Algorithm] 알고리즘 공간복잡도에 대하여

 

빅-오 표기법

시간 복잡도에는 여러 개념이 있지만 그중에서 ‘아무리 많이 걸려도 이 시간 안에는 끝날 것‘의 개념이 제일 중요합니다. 예를 들어 동전을 튕겨서 뒷면이 나올 확률을 이야기해본다면 운이 좋으면 한 번에 뒷면이 나올 수도 있고 운이 좋지 않으면 3번 4번만에 뒷면이 나올수도 있습니다. 운이 나쁜 경우 n번만큼 동전을 튕겨야 하는 최악의 경우가 발생하는데 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 부르며 이 방식을 가장 많이 사용합니다.

 

시간 복잡도 그래프

 

O(1) (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.

O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.

O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.

O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.

 

※ 여기서 n이란 입력되는 데이터를 의미합니다.

 

시간복잡도 계산

printf("hello");

일반적인 프로그램이 1라인이 실행되는 것은 1이라고 표현합니다. 위의 시간 복잡도는 O(1)입니다.

 

for(int i=0;i<input;i++){
    printf("hello");
}

반복문이 N번만큼 반복하므로 위의 복잡도는 O(n)입니다.

 

for(int i=0;i<input;i++){
    printf("hello");
}
for(int i=0;i<input;i++){
    printf("hello");
}

N번만큼 반복하는 반복문이 2개가 있습니다. 착각할 수도 있지만 O(n²)이 아닌 O(n)입니다. 시간 복잡도 계산에는 가장 큰 영향을 미치는 알고리즘 하나만 시간복잡도를 계산합니다. O(n) 반복문이 하나가 있으나 2개가 있으나 수십개가 있으나 O(n)입니다.

 

for(int i=0;i<input;i++){
    for(int j=0;j<input;j++{
        printf("hello");
    }
}

 N번만큼 반복하는 이중 for문이 있으므로 위 소스의 시간 복잡도는 O(n²)입니다.

 

for(int i=0;i<input;i++){
    for(int j=i;j<input;j++{
        printf("hello");
    }
}

위의 경우에는 내부 for문의 변수 j의 값이 i 이므로 엄연히 이중 for문보다 시간이 적게 걸리지만 그래도 시간 복잡도는 O(n²)입니다. 시간복잡도 계산에서는 정확한 값을 산출하는 것이 아니라 근사치를 계산하기 때문입니다.

 

for(int i=0;i<input;i++){
    for(int j=i;j<input;j++{
        printf("hello");
    }
}
for(int i=0;i<input;i++){
    printf("hello");
}

이중 for문 1개와 for문 1개가 있습니다. 이때는 시간 복잡도에 영향을 더 많이 끼치는 이중 for문 하나만 계산하여 시간복잡도는 O(n²)입니다.

 

시간복잡도 줄이는 법

앞서 말씀드렸지만 동일한 동작을 수행하는 알고리즘은 최대한 시간이 적게 걸리는 것이 좋습니다. 시간 복잡도를 줄이는 방법은 다양한 방법이 있을 텐데요. 위에서 예상하셨을 수도 있을 텐데 시간 복잡도에서 반복문이 가장 시간 소모에 가장 큰 영향을 미칩니다. 그렇기에 시간 복잡도를 줄이는 방법은 반복문의 숫자를 줄이는 것입니다. 

 

또 다른 방법이라고 함은 자료구조를 적절하게 이용하는 방법입니다.  위 표에 자료구조에 대한 시간 복잡도가 잘 나와있으니 가장 효율적인 자료구조들을 적절히 사용한다면 시간 복잡도를 최대한 줄일 수 있습니다.

 

마지막 방법은 알고리즘을 적절하게 이용하는 것입니다. 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있을 텐데요. 효율적인 알고리즘을 공부해뒀다가 적절할 때 사용한다면 큰 효과를 볼 수 있습니다. 위의 표는 대표적인 배열의 정렬 알고리즘의 시간 복잡도를 나타냅니다. 

 

실행 시간 예측하기

위로 갈수록 알고리즘이 매우 빨라지며 아래로 갈수록 nn의 값이 커지고 급격하게 알고리즘의 수행 시간이 증가합니다. 대략 컴퓨터가 1억 번의 연산을 하기 위해서는 1초 정도의 시간이 필요합니다. 만약 1만번의 입력데이터가 들어온다면 O(n)의 경우에는 0.1초 O(n²)의 경우 1만 * 1만 = 1억이므로 대략 1초정도의 시간이 필요하겠습니다. 만약 1억 개의 데이터가 들어오는데 실행시간이 1초인 알고리즘 문제를 풀려면 무조건 O(n)이나 O(Log N)의 시간 복잡도로 문제를 풀어야 한다는 이야기겠죠?