개발자로 살아남기

시간복잡도란?

(Time Complexity)

시간복잡도라는 말 자체가 뭔가 되게 모순되어 보인다.. 그래도 한 번 살펴보자.

시간복잡도 (Time Complexity)

 - 입력 데이터가 특정 알고리즘을 거쳐 결과가 나오는데 걸리는 시간을 의미

   여기서 "시간"은 정확히 몇 초 걸린다! 그런 의미가 아닌 데이터의 증가에 따른 시간(연산속도)의 증가 정도를 의미

 - 시간복잡도는 대입연산, 사칙연산, 비교구문, 함수호출 등의 연산을 기준으로 계산

 - 시간복잡도는 최선, 평균, 최악의 경우로 나눌 수 있음

빅-오(Big-O) 표기법

 - 단순히 시간복잡도를 표현한 다항식에서 최고차항의 차수가 빅-오가 된다.

 - 예를들어, 100n^3 + 99999n^2 + 888 이라는 시간복잡도를 가진 함수가 있을 때, 이 다항식을 빅-오 표기법으로 표현하면 O(n^3)이 된다. 99999n^2도 상당히 큰 수인데 제외하는 이유는 단순히 시간복잡도는 위에 언급한 것처럼 데이터의 증가에 따른 시간(연산횟수)의 증가 정도를 표현하기 때문이다. 

빅-오(Big-O) 표기법에 따른 계산방법

 - 다음과 같은 코드가 있을 때의 시간복잡도를 빅-오로 표현하면 어떻게 될까?

for(int i=0; i<sizeof(arr)/sizeof(int); i++){
	if (arr[i] == 7){
    	printf("7 => index %d\n", i + 1);
        break;
    }
}

배열 arr의 크기를 모르며 어떤 데이터가 들어있는지 모른다는 최악의 상황을 가정하고 구해보면 다음과 같다.

연산을 기준으로 시간복잡도를 구한다고 했으니

이 된다. 따라서 위 코드의 시간복잡도는 T(n) = 3n + 1이 되며, 이를 빅-오로 표현하면 최고차항의 차수인 O(n)이 된다.

마지막으로 아래 사진은 대표적인 빅-오 이다.

자료구조와 각 정렬 방법의 빅-오는 아래 사이트를 참고하면 된다.

https://www.bigocheatsheet.com/