시간 복잡도

 이전에 알고리즘의 복잡도에 대해 잠깐 알아보았는데

 

그 복잡도 중 시간 복잡도에 대해 더 자세히 알아보려고 한다.

 

공간 복잡도의 경우 해당 알고리즘이 얼마나 많은 메모리 공간을 필요로 하는지 어느 정도 이해할 수 있는데

 

시간 복잡도의 경우 반복문이 얼마나 겹쳐 있는지, 또 어떻게 도출해 나가는지에 따라 시간 복잡도가 달라지기 때문에 

 

직관적으로 바로 파악하기 힘든 경우가 많다. 

 

또한 하드웨어 환경에 따라 처리시간이 달라지기도 하고, 소프트웨어 환경에 따라 처리시간이 달라지기도 한다. 

 

이를 단순한 함수로 표현하기 위해서 점근적 표기(Asymptotic Notation)를 사용한다.

 

이는 입력 크기인 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.

 

이러한 표기에는 크게 

 

O(Big-Oh) 표기법

Ω(Big-Omega)표기법

Θ(Big-Theta)표기법이 있다.

 

- O(Big-Oh)표기

 

O 표기는 복잡도의 점근적 상한을 나타낸다.

 

복잡도를 따질 때는 가장 큰 차수 항의 계수를 쳐낸 뒤 작성하기 때문에 만약 2n^3+3n+1 의 복잡도를 가진다면

 

O 표기는 O(n^3)이다.

 

그도 그럴 것이 n이 무한대로 커질 때 최고 차항을 제외하고는 의미가 없어지고, 계수 또한 의미가 없어지기 때문이다.

 

만약 시간 복잡도가 O(n^2)인 알고리즘이 있다면 실행시간이 n^2에 비례한다고 볼 수 있다. 

 

시간 복잡도가 n^2인 알고리즘은 

 

간단하게 이중 for 문을 들 수 있다.

 

int sum=0;

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

이런 코드가 있다고 치면

 

i가 0부터 n-1까지 매번 j는 0부터 n-1까지 돌기 때문에 (n-1)+(n-1)+... = (n-1)(n-1)이 된다.

 

즉 최고 차항은 n^2이 되기 때문에 시간 복잡도가 n^2인 것이다.

 

 

 

- Ω(Big-Omega)표기

 

Ω 표기는 복잡도의 점근적 하한을 의미한다.

 

이는 O 표기와 반대로 '최소한 이정도는 걸린다'라는 뜻이다.

 

위와 같이  2n^3+3n+1 의 복잡도를 가진 알고리즘이 있다면

 

Ω 표기는 최소한 이정도는 걸린다라는 의미로 쓰기 때문에 Ω(n^3)으로 쓸 수 있다. 

 

 

 

- Θ(Big-Theta)표기

 

Θ 표기는 O 표기와 Ω 표기가 같은 경우 사용한다. 

 

Θ 표기는 평균적인 경우를 가정할 때 사용하고, 동일한 증가율을 가진다 라는 의미로 표현할 수 있다.

 

 

 

쉽게 말하자면 

 

Big Oh 표기는 최악의 경우를 상정할 경우,

 

Big Omega 표기는 최선의 경우를 상정할 경우,

 

Big Theta 표기는 평균적인 경우를 상정할 경우에 사용할 수 있다.

 

일반적으로 Big Oh 표기를 많이 쓰는데 

 

최악의 경우의 시간을 줄여야 할 경우가 많기 때문이다.

 

알고리즘 문제를 풀 때도 시간초과가 날 경우 Big Oh 표기의 시간 복잡도를 기준으로 뜯어 고친다. 

 

 

 

많이 쓰이는 Big Oh 표기는 다음과 같다.

 

O(1) : 상수 시간

O(logn) : 로그 시간

O(n) : 선형 시간

O(nlogn) : 로그 선형 시간

O(n^2) : 제곱 시간

O(n^3) : 세제곱 시간

O(2^n) : 지수 시간

 

 

제곱 시간이 넘어가면서 부터는 웬만한 알고리즘 문제 같은 경우 시간 초과가 날 확률이 높아지니 

 

시간 복잡도를 생각해 가며 설계를 하는 것이 중요하다.

 

 

라고 이해했다.