시간복잡도

이 글은 공부한 내용을 기반으로 정리하는 글이오니 건전한 비판은 환영합니다.

 

시간 복잡도는 왜 알아야 할까?

같은 프로그램을 작성하였을 때 A라는 사람과 B라는 사람이 하나의 목표를 두고 작성을 하였다.

A라는 사람의 프로그램을 실행하였을 때 3초가 걸리고, B라는 사람의 프로그램을 작성을 하였을 때 시간이 10초가 걸린다면 A라는 사람의 프로그램이 빠르기 때문에 1차원 적으로는 A의 시간이 더 빠르다.

시간 복잡도를 아는 방법은 먼저 프로그램을 돌리고 시간을 측정하였을 때, A-Z까지 시간으로 순서를 나누었을 때 일렬적으로 나눠질 수 있다. 즉 같은 입력을 제공하였을 때 어느 프로그램이 가장 빠를 수 있나 측정하는 것이 시간 복잡도이다.

 

빅 오 표기법

빅오 표기법이란? 시간에 가장 큰 영향을 주는 시간을 계산하는 것이다.

무슨 이야기냐면

int main(){
	int a,b;
    int c;
    scanf("%d %d",&a, &b);
    
    c = a+b;
    
    printf("%d",c);


	return 0;
}

위에서 로직을 보면 총 6번 줄의 코드를 작성하여 마지막에 c가 출력이 된다.

그러면 O(6) 즉 6번을 실행한다고 이야기 하지만, 여기서는 그렇게 큰 로직 덩어리는 없기 때문에 O(1)이라고 이야기 할 수 있다.

 

만약에 O(n+2)라고 하였을 때, 시간 복잡도는 어떻게 될까? 앞에 나온것을 기준으로 O(n)으로 이야기 할 수 있다.

왜냐하면, n자리에 100개, 1000개, 10000개가 들어올 수 있으므로 중요한 것은 n이 결정적인 시간에 영향을 주기 때문에 O(n)으로 이야기 할 수 있다.

 

int main(){
	int n;
	int sum;
	scanf("%d ",&n);
    

    for(int i = 0 ; i<n ; i++){
    	for(int j = 0 ; j<n ; j++){
        	sum += i+j;
        
        }
    }



	return 0;
}

위와 같이 sum을 구하기 위해 이중 for문을 작성 하였다. 이것은 어떻게 표현될 수 있을까? 

O(n2)로 표현할 수 있다.

만약에 이런 방식이면?

int main(){
	int n;
	int sum;
	scanf("%d ",&n);
    

    for(int i = 0 ; i<n ; i++){
    	for(int j = i ; j<n ; j++){
        	sum += i+j;
        
        }
    }



	return 0;
}

j가 i에 따라서 유동적으로 바뀌지만 1+.......+n 까지기 때문에 결과적으로 O(n2+n/2)로 나타나지만 O(n2)로 표현할 수 있다.

가장 중요한 것은 n이 시간 복잡도에 가장 큰 영향을 준 것이기 때문이다.

 

그래서 언제 사용할 것인가?

많은 경우의 수가 있겠지만, 여기서 설명하고자 하는 것은 알고리즘 문제를 풀 때 설명하는 것 입니다.

여기서 의문점이 드는 것은 과연 시간복잡도를 계산 한다고 해서 다 시간이 맞을까?입니다

답은 "아니다" 입니다. 왜냐하면 시간복잡도를 계산하는 것은 대략적인 시간을 계산하는 것이기 때문입니다.

그래도 왜 계산을 해야하냐면? 최악의 경우를 계산을 해봐야 하기 때문입니다.

그게 무슨이야기 냐면

int main(){
	int n;

	scanf("%d ",&n);
    

    for(int i = 0 ; i<n ; i++){
    	if(i*i>n){
        	break;
        }
    }



	return 0;
}

이 경우에는 n이 입력을 얼마 받나가 가장 중요합니다. 그렇기 때문에 계산을 해봐야 합니다.