시간복잡도

지금까지 알고리즘을 공부하면서 구조를 이해하고 넘어갔었는데 매번 볼때마다 시간복잡도에 대한 이야기가 있어서 제대로 찾아봐야겠다는 생각을 하게 되었다.

 

---

시간복잡도

입력값이 변화에 따라 연산을 실행할때, 연산 횟수에 대비 걸리는 시간을 의미. 즉 효율적인 알고리즘이란 이 연산이 증가함에 따라 이 시간이 얼마나 적게 걸리는지를 이야기한다. 이 시간복잡도 표기법은 '빅-오(Big-O)' 표기법을 사용한다고 한다.

 

표기법 빅(Big)

- Big-O(빅-오) : 상한 점근(최악)

- Big-Ω(빅-오메가) : 하한 점근(최선)

- Big-θ(빅 세타) : 둘의 평균(중간)

 

이러한 표기법이 있는데 시간복잡도에서는 빅-오 표기법을 사용하는 이유는 최악의 경우 이정도까지 시간이 걸린다를 고려해야하기 때문이라고 한다.

 

빅-오(Big-O) 표기법 종류

• O(1) : 일정한 복잡도. 입력값이 증가하더라도 시간이 증가하지 않음. (입력 즉시 값을 얻을 수 있다.)
• O(n) : 입력값이 증가함에 따라 시간이 같은 비율로 증가하는 선형 관계. (1개 1초 -> 100개 100초. for문)
• O(log n) : O(1)다음으로 훌륭한 시간복잡도. 대표적인 예시는 BST(Binary Search Tree). (1~100 숫자 맞추기 Up/Down)
• O(n^2) : 입력값이 증가함에 따라 시간이 제곱으로 증가하는 관계.(1개 1초 -> 10개 100초. 다중 for 문)
• O(2^n) : 가장 느린 알고리즘. 매번 진행할때마다 2배씩 증가한다. (재귀로 구현된 피보나치 수열)