[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)의 시간 복잡도로 문제를 풀어야 한다는 이야기겠죠?

 

 

하나 더 알아가기

공간복잡도란?

공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다.

 

시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다.

 

문제점

재귀함수일 경우에는 이야기가 달라집니다. 위의 예제를 보시면 함수의 인자값 n에 따라 공간복잡도가 달라집니다. 함수 내부에서 n이 1이하일때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 위의 공간 복잡도는 O(n)입니다.

 

공간복잡도를 줄이는 방법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.

​프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.

1. 고정 공간
2. 가변 공간

 

시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다. 또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에 ​만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로  짜는게 더 효율적이라고 볼 수 있습니다.

 

참조사이트 : coding-factory.tistory.com/608?category=794828