[알고리즘] 점근성능

#1 점근성능

입력크기(실제 처리하는 데이터 개수) n이 무한대로 커짐에 따라 결정되는 성능!

데이터 개수가 증가하면 알고리즘 성능결정에 가장 큰 요인은 무엇인지 따지는 것!

	f(n) = 10n + 9	f(n) = n^2 / 2 + 3n
n=5	59	27.5
n=10	109	80
n=15	159	157.5
n=16	169	176
n=20	209	260
...	...	...

수행시간의 다항식 함수에서,

데이터 개수가 증가할 수록(입력크기가 증가할 수록) 최고차항이 성능결정요인에 가장 큰 요인이 됨

계수없이 최고차항만으로 시간복잡도를 표현!

수행시간의 어림값이나 수행시간의 증가추세 파악이 용이하다 => 알고리즘의 우열을 표현!

#2 점근성능 표기법

[정의1] 'Big-oh' 점근적 상한 ( O => 최악의 수행시간을 나타내기 위한 표기법)

어떤 양의 상수 c와 n0(데이터의 개수)가 존재하고, 

모든 n ≥ n0에 대하여, f(n) ≤ c · g(n) 이면, 

f(n) = O(g(n))

f(n)(내가 구한 알고리즘의 수행시간)이 어떤양의 상수와 g(n)의 곱보다 작거나 같다면,

f(n) = O(g(n))이다.

[정의2] 'Big-omega' 점근적 하한 ( Ω => 최선의 수행시간을 나타내기 위한 표기법)

어떤 양의 상수 c와 n0(데이터의 개수)가 존재하고, 

모든 n ≥ n0에 대하여, f(n) ≥ c · g(n) 이면, 

f(n) = Ω(g(n))

f(n)(내가 구한 알고리즘의 수행시간)이 어떤양의 상수와 g(n)의 곱보다 크거나 같다면,

f(n) = Ω(g(n))이다.

이 때, c · g(n) 은 f(n)의 하한이 된다. 즉 알고리즘 성능이 아무리 좋더라도 f(n)보다 좋아질 수 없다.

[정의3] 'Big-theta' 점근적 상하한 ( θ => 상한과 하한 모두 존재)

어떤 양의 상수 c1, c2와 n0(데이터의 개수)가 존재하고, 

모든 n ≥ n0에 대하여, c1 · g(n)  ≤ f(n) ≤ c2 · g(n) 이면, 

f(n) = θ(g(n))

∴ 알고리즘 수행시간을 좀더 엄밀히 알 수 있다.

#3 주요 O-표기 간 연산 시간의 크기관계

상수 시간 < 로그 시간 < 선형 시간 < 로그 선형 시간 < 제곱 시간 < 세제곱 시간 < 지수 시간

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

← 효율적    |    비효율적 →

- 상수시간은 데이터 개수와 무관하게 수행시간이 항상 일정

#4 알고리즘의 시간복잡도 구하기

- 알고리즘 수행시간 f(n)을 구한 후 f(n)=O(g(n))을 만족하는 최소차수의 함수 g(n)을 찾자

- 알고리즘에 나타난 루프의 반복횟수를 조사★ => 시간복잡도로 취하자!

- g(n)은 최고차수에 의존함

알고리즘 수행시간에 가장 큰 영향을 주는 것은 반복루프이다!

첫번째 알고리즘의 수행시간 f(n)은 3n + 2    

=> O(n) 선형시간

두번째 알고리즘의 수행시간 f(n)은 n^2        

=> O(n^2) 제곱시간

(∵ 이중반복문은 시간복잡도 ↑ =>  효율 ↓)