[알고리즘] 복잡도 구하기

복잡도란?

알고리즘의 성능을 객관적으로 평가하는 기준이다.

 

복잡도 종류

 

1. 시간 복잡도 : 실행에 필요한 시간을 평가하는 것
2. 공간 복잡도 : 기억영역과 파일 공간이 얼마나 필요한가를 평가하는 것

 

복잡도 구하는 방법

 

처음 한번만 실행하는 경우 : O(1) 이라고 표기한다.

n에 비례하는 횟수만큼 실행하는 경우 : O(n) 이라고 표기한다.

 

실행횟수	복잡도
1	O(1)
n/2	O(n)
n	O(n)

 

컴퓨터는 n / 2번이나 n번이나 똑같다.

 

 

 

 

 

 

 

2개이상의 복잡도 구하기

 

2개이상의 복잡도를 구하는 식은 다음과 같다. 

더 높은 쪽의 복잡도를 우선시 한다. 

전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.

O(f(n)) + O(g(n) = O( f(n) , g(n) )

<복잡도 대소관계>

 

1  <  log n  <  n log n  <  n^2  <  n^3  <  n^k  <  n^n 

 

 

예시

 

 

 

 

1번 복잡도 : 한번만 계산 해도 되니까 O(1)

2번 복잡도 : 역시 O(1)

3번 복잡도 : O(n)

4번 복잡도 : O(n)

5번 복잡도 : O(n)

6번 복잡도 : O(1)

 

가장 큰 복잡도 기준 : O(n) 이다.

 

n은 반복횟수를 나타낸다.