시간복잡도

시간 복잡도(time complex)

시간 복잡도란 어느 코드를 실행했을 때 실행 시간이 어느정도일지 표현해 보는 것이다.

여기서 실행시간이랑 함수/알고리즘 수행에 필요한 스텝(step) 수 이다.

int[] multiply(int[] inputs, int multiplier) {
	int[] nums = new int[inputs.length];
    
    for(int i = 0; i < inputs.length; i++) }
    	nums[i] = inputs[i] * multiplier;
    }
    return nums;
}

위와 같은 코드가 있을 때 각각 라인이 실행되는 스텝은 상수로 표시된다. 따라서 각 라인의 스텝수와 실행시간은 아래와 같이 정리할 수 있다.

cost	times
c1	1
c2	N+1 (for 문을 돌고 빠져나올때 한번 더 실행되기 때문에)
c3	N
c4	1

이렇게 정리된 것을 수식으로 정리하면

 

T(N) = c1 + c2 * (N+1) + c3 * N + 1

         = (c2 + c3) * N + c1 + c2 + 1 

         = a * N + b (위의 식을 치환하였다) 여기서 N 은 input의 Size 에 해당한다.

 

위의 식을 정리하면 

• 여기서 더 정확한 계산은 어렵다
• N이 작을땐 실행 시간이 의미가 없다

그럼 여기서 N -> 무한대일 때 실행 시간은 어떻게 될까?

• N이 커질수록 덜 중요한 것은 제거된다
• 최고차항만 의미있다.
• 최고차항의 계수는 의미가 없다. (위의 식에서 a 부분)

라는 사실을 알게된다. 이를 점근적 분석이라고 하며, 임의의 함수가 N -> 무한대일 때 어떤 함수 형태에 근접하는지 분석하는 것이다.

 

다시 정리해

 

시간 복잡도는 함수의 실행 시간을 표현하는 것이고, 주로 점근적 분석을 통해 실행 시간을 단순하게 표현하며 이때 점근적 표기법으로 표현한다.

 

boolean exists(int[] inputs, int target) {
	for (int i = 0; i < inputs.length; i++) {
    	if(inputs[i] == target) {
        	return true;
        }
    }
    
    return false;
}

위와 같은 코드가 있을 때 함수의 파라미터 데이터에 따라 실행시간이 조금씩 달라지게 된다. 만약 target 이 앞쪽에 있다면 실행 시간이 짧게 걸리고, 뒤에 있다면 길게 걸릴 것이다. 이런 경우  case 정리가 필요하다

case	when	times
best	0번째에 존재	1
worst	마지막에 존재 or 존재하지 않음	N

따라서

함수의 실행 시간은 아무리 빨라도 상수 시간 이상 or 함수 실행 시간은 아무리 오래 걸려도 N에 비례하는 정도 이하

이기 때문에 

O(N) 점근 표기법으로 표현할 수 있다.