(Data Structure) 알고리즘의 시간복잡도

알고리즘의 시간 복잡도

앞에서 학습한 단계 수를 이용해 알고리즘의 시간 복잡도에 접근 할 수 있다.

여기에는 3가지 표기 방법이 있다.

O, Ω, θ

• O-표기법 (big-oh notation)

어떤 알고리즘의 총 단계 수의 함수를 f(n) 이라 하자.

f(n) <= cg(n)

위 식의 조건을 만족하는 가장 작은 값을 가지는 g(n) 함수를 사용해 f(n) 의 시간 복잡도를 O(g(n)) 으로 표현할 수 있다.

이 표기법에서는 시간 복잡도가 제일 크다는 것을 실행 기간이 제일 길다는 것으로 해석하여 최악의 경우로 해석한다. 즉, 클수록 안좋은것이다.

말로만 이해하기에는 어렵다 생각하므로 몇 가지 예시를 생각했다.

f(n) = 3n³ - 2n² + 8
g(n) = n³

이때, 3n³ - 2n² + 8 <= 3(n³) 이므로 f(n) 의 시간복잡도는 O(n³) 이 된다.

이런 방식으로 구한 O(g(n))을 통해 알고리즘의 시간복잡도를 비교할 수 있다.

여기서 g(n) 으로 나올 수 있는 종류는

상수, 로그, 1차식, 2차식, 3차식, 지수 가 있는데

각각의 함수 그래프를 통해 시간 증가율을 알 수 있다.

• Ω-표기법 (big-omega notation)

이 표기법은 앞서 말한 O-표기법과 반대로

f(n) >= cg(n)

의 조건을 이용해 f(n) 이 가질 수 있는 제일 작은 g(n) 을 이용해 시간복잡도가 제일 작은 최선의 경우로 해석한다. 즉, 작을수록 좋은것이다.

O-표기법과 사용법이 비슷하다.

조건을 만족하는 가장 작은 값의 g(n) 함수를 선택하여 Ω(g(n)) 으로 표기한다.

f(n) = 3n³ - 2n² + 8
g(n) = n³

위와 같은 예시에서

3n³ - 2n² + 8 >= 3(n³) 이므로 f(n) 의 시간복잡도는

Ω(n³) 이 된다.

• θ-표기법 (big-theta notation)

c₁g(n) <= f(n) <= c₂g(n)

위 조건은 f(n)이 가질 수 있는 상한 값이 c₂g(n), 하한 값이 c₁g(n) 이라는 것을 의미하는데,

상한 값과 하한 값을 나타내는 함수가 g(n)으로 동일할때에는 시간 복잡도를 ‘평균적인 경우’ 라 하고

θ(g(n))으로 표현한다.

3(n) <= 3n + 4 <= 4(n) 

이와 같이

상한 값과 하한 값의 g(n)이 모두 n 으로 같으므로

θ(n) 으로 나타낼 수 있고 평균적인 경우라 부른다.

공부하면서 이 부분이 유난히 흥미로웠다.

그냥 단순히 코드로만 봤던 것들이 이렇게 논리적으로 해석되는 것에서

마치 자연속에서 엄청난 발견을 이룬것 같은 느낌을 받았다.

이번 내용 설명을 너무 못한것 같다.

확실히 내가 이해하는 거랑 말로 설명해보는거랑은 다르다고 느낀다…

어쩌면 이해를 완벽히 못 했는지도……..

그래도 이해한 범위내에서 설명해봤다…@@