[Algorithm with C] Time complexity (시간복잡도)

Time complexity(시간복잡도)

시간복잡도란 어떠한 크기의 입력값 n에 대해 알고리즘을 수행하는 동안 (시간) 몇 번의 연산을 

실행했는지를 점근 표기법을 이용해 나타낸것이다.

 

예를 들어 1부터 n(100)까지의 합을 구하는 프로그램을 작성해본다면

#include <stdio.h>

int main() {
    int n , result =0;
    scanf("%d",&n);
    for (int i = 1;i<=n;i++) {
        result +=i;
    }
    printf("%d",result);
    return 0;
}

for문을 사용해 result에 1부터 100까지의 값을 넣는 방법과

#include <stdio.h>

int main() {
    int n , result =0;
    scanf("%d",&n);
    result = n*(n+1)/2;
    printf("%d",result);
    return 0;
}

1부터 n까지 자연수들의 합을 구하는 공식인 n(n+1)/2를 사용에서 합을 계산하는 방법이 있다.

첫번째 방법은 1부터 100가지 총 100번의 연산을 수행하지만 두 번째 방법에서는 덧셈,곱셈,나눗셈 총 3번의 

연산으로 답을 구할 수 있다. n값이 증가해도 관계 없이 3번의 계산이 처리된다.

 

위와 같이 알고리즘은 입력되는 데이터 크기(또는 갯수)에 따라 계산 횟수 수행 시간이 달라지게 된다. 

계산 횟수의 정확한 측정은 어려워 Big O 표기법을 사용해 표시한다.

 

예시로 입력 데이터 갯수가 n개일때 2n+7번 계산하는 알고리즘과 2n번 계산하는 알고리즘이 있다면

n이 커지면 둘 사이의 차이는 없어진다(거의). 이를 Big O 표기법으로 나타내면 O(2n+7) = O(2n)이다.

(대충 Big O 표기법은 상수만큼의 시간 차이는 무시하는 느낌)

 

크기 n의 데이터가 입력될때 n^2번 계산해서 답을 내는 알고리즘과 1000n번 계산해서 답을 내는 알고리즘을 

비교해보면 n = 10일 때는 1000n번 계산 하는 알고리즘이 100배 더 느릴 수도 있지만 n = 1000만 되어도 두 알고리즘의

속도가 비슷해지고 n = 100000일 경우 n^2번 계산하는 알고리즘이 100배 느려짐.

 

대충 정리를 해보자면 계산 횟수에 붙은 상수는 별로 중요하지 않다. 1000이라는 상수가 무색해질 정도로 n이 커지면 

그 때는 n이 커짐에 따라 증가하는 계산 횟수가 더 중요하다. 때문에 시간복잡도를 나타낼때 n번 계산하던 5n + 1256번 계산하든, 176534n번 계산하든 모두 O(n)으로 나타내는것.

예시로 3^n + 2n^3 + 12451n^2 + 33n log n + 151511번 계산하는 알고리즘의 시간 복잡도는 O(3^n)로 간단히 나타낼 수 있음. 

시간 복잡도	설명
O(1)	상수 형태, n의 값에 상관없이 일정한 양의 계산만 함
O(log n)	로그 형태
O(n)	선형
O(n log n)	선형로그
O(n^2),O(n^3),...	다차 형태
O(2^n)	지수 형태
O(n!)	팩토리얼