[알고리즘] 시간복잡도

알고리즘에서 시간복잡도란 입력값의 변화에 따라 연산을 실행할 때, (핵심)연산의 횟수에 비해 시간이 얼만큼 걸리는지를 함수로 나타낸 것을 말한다.

빅오

• f(n)=0(g(n))은 g(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 크다는 것을 의미
• 반드시 넘지 않는 최대일 때의, 최악을 나타내는 시간 복잡도

빅오메가

• f(n)=오메가(g(n))은 반드시 실행해야 되는 수
• 최소한으로 실행해야 하는 수

빅세타

• 빅오메가와 빅오가 같을 때
• 최적의 알고리즘
• ex) 해시함수

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

i는 k배씩 커진다.
전체 알고리즘 횟수는 수학적으로는 i는 k배만큼 커지며 n에 도달하고 있기 때문에 log(k) n, 로그 베이스는 빅오에서 사실상 log n으로 보므로 log n 이다.