시간복잡도(Time Complexity)란?

시간복잡도란?

(Time Complexity)

---

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

 

시간복잡도 (Time Complexity)

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

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

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

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

 

최선의 경우(빅-오메가, Big-Ω)	- 최선의 상황을 기준으로 시간복잡도를 측정  - 대부분의 알고리즘은 빅-오메가로 시간복잡도를 측정했을 때 만족할만한 결과가 나와 실제로 잘 쓰이지 않음.  - 예를들어, 특정 배열을 탐색하는 알고리즘에서 찾고자하는 값이 첫번째로 있을 경우
평균의 경우(빅-세타, Big-θ)	- 평균적인 상황을 기준으로 시간복잡도를 측정  - 평균적인 상황이 무엇인가?에 대한 문제가 발생  - 간단한 알고리즘의 경우에는 구하기 쉽지만, 조금만 복잡해질 경우 경우의 수가 많아져 평균적인 상황을 구하기 어려움  - 빅-오 보다는 많이 쓰이지않지만 어느정도 쓰이는 것으로 보임  - 예를들어, 동전 하나를 100회 던졌을 때 앞, 뒤가 나온 횟수의 평균적인 상황,    앞, 뒤가 나올 확률이 무조건 50%인 상황 등
최악의 경우(빅-오, Big-O)	- 최악의 상황을 기준으로 시간복잡도를 측정  - 최악의 상황을 기준으로 측정을 하게되면 입력데이터의 개수가 많더라도 이정도의 성능은 보장한다는 뜻이 됨  - 대부분 알고리즘의 시간복잡도를 표현할 때 빅-오 로 표현함  - 예를들어, 특정 배열에서 탐색 알고리즘을 이용해 탐색할 때 찾고자 하는 값이 배열에 없을 경우

빅-오(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의 크기를 모르며 어떤 데이터가 들어있는지 모른다는 최악의 상황을 가정하고 구해보면 다음과 같다.

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

 

int i = 0 => 1회 연산 i<sizeof(arr)/sizeof(int) => n회 연산 i++ => n회 연산 arr[i] == 7 => n회 연산

 

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

 

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

<빅-오에 따른 증가형태>

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

 

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell