시간복잡도(Time Complexity)

백준사이트에서 시간복잡도를 마주쳐서 문제 풀기전에 정리

정보처리기사를 준비할 때 O(n) 이나 O(log n), O(n2) 등을 보긴했는데 외우기에 급급했기 때문에...

 

시간복잡도란?
   알고리즘을 평가할 때 사용하는 것으로 연산 횟수에 비해 시간을 얼마나 소모하는가에 대한 평가를 말함.
   시간복잡도를 표기하는 방법에는  Big-O(상한선 기준), Big-Ω(하한선 기준), Big-Θ(이 둘의 평균 기준)이 있다.
   보통 빅-오 표기법(Big-O)을 사용해서 표현한다.

 

빅-오 표기법(Big-O)
   알고리즘은 값이 클수록(=그래프가 위로 올라갈수록) 비효율적이다.
   빅오표기법은 상한선을 기준 = 최악의 경우를 고려 = 이 시간까지 걸릴 수 있다

 

빅오 표기법의 종류 : ((효율 좋음)) O(1) > O(log n) > O(n) > O(n log n) > O(n^2) > O (2^n) ((효율 나쁨))

                                                      (상수함수 > 로그함수 > 선형함수 > 다항함수 > 지수함수)

 

1. O(1) : 일정한 복잡도를 가짐 = 입력값이 증가해도 시간은 증가하지 않음

 ex) 스택 Push, Pop

2. O(log n) :데이터가 2배로 증가할 때, 연산수가 1 단계 씩 증가

 ex) 이진트리

3. O(n) : 같은 비율로 복잡도가 증가

 ex) for문

4. O(n log n)

 ex) 퀵 정렬, 병합 정렬, 힙 정렬

5. O(n^2) : 복잡도가 제곱으로 증가함

 ex) 이중 for문, 삽입 정렬, 거품 정렬, 선택 정렬

6. O (2^n) : 기하급수적으로 증가하는 복잡도(2의 n제곱만큼 증가)

 ex) 피보나치 수열