런타임

[algorithm] 시간 복잡도 계산 방법 + 표기법

효율적인 알고리즘을 짜기 위해선 런타임과 메모리 사용을 최소화시키는 것이 중요하다. 그 중 런타임, 즉 시간 복잡도를 계산하는 법을 먼저 알아보겠다. 표기법 시간복잡도 표기 방식에는 아래와 같이 세가지가 있다. 최상의 경우: 오메가 표기법 (Big-Ω Notation) 최악의 경우: 빅오표기법 (Big-O Notation) 평균의 경우: 세타 표기법 (Big-θ Notation) 일반적으로 가장 많이 사용되는 것은 빅오 표기법이다. 빅오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. (예, 2n²-2n+2 > O(n^2)로 표기) 빅오 표기법이 개발자들에게 중요한 이유는, 최악의 경우를 대비해서 알고리즘을 짜야하기 때문이다. 빅오 표기법에 가장 큰 영향을 미치는 것은 input의 개수이다. In..