[알고리즘] Analysis of Algorithms

Time complexity analysis

시간복잡도 분석은 input size에 대해 basic operation(단위 연산)이 얼마나 많이 수행되었는지 구하는 것이다.

시간복잡도 분석 방법에는 Every-case analysis, Worst-case analysis, Best-case analysis, Average-case analysis가 있다.

시간복잡도는 알고리즘의 효율성을 판단하기 위해 자주 사용된다.

 

++단위연산(basic operation): 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여, 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록한다. 이 명령문 또는 명령문 군을 단위연산이라 한다. ex) 비교, 할당

Every-case analysis(ECA)

입력크기 n에만 종속, 입력값과는 무관, E(n)

ex) 단순히 배열 S에 자연수 원소들을 더하는 경우

Worst-case analysis(WCA)

입력 크기 n, 입력값 모두 종속, W(n)

basic operation이 수행되는 횟수가 최대일 때를 구하는 것이다.

시간복잡도 분석할 때 가장 많이 사용된다.

Best-case analysis(BCA)

입력 크기 n, 입력값 모두 종속, B(n)

basic operation이 수행되는 횟수가 최소일 때를 구하는 것이다.

Average-case analysis(ACA)

입력 크기 n, 입력값 모두 종속, A(n)

모든 입력에 대해 단위연산이 수행되는 평균을 구한다.

확률을 바탕으로 계산된다.

 

Order function

f(n), g(n) - complexity function, parameter는 input size

O(f(n), Ω(f(n)), Θ(f(n)) - order function, parameter는 complexity function

O(f(n)) - Big O, Asymptotic Upper Bound

주어진 복잡도 함수 f(n)에 대해서, O(f(n))은 n ≥ N을 만족하는 모든 n에 대해 g(n) ≤ c x f(n)을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

 

아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. → 상한

Ω(f(n)) - Big Ω, Asymptotic Lower Bound

주어진 복잡도 함수 f(n)에 대해서, Ω(f(n))은 n ≥ N을 만족하는 모든 n에 대해 g(n) ≥ c x f(n)을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

 

아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. → 하한

Θ(f(n)) - Big Θ, Asymptotic Tight Bound

주어진 복잡도 함수 f(n)에 대해서,Θ(f(n))은 n ≥ N을 만족하는 모든 n에 대해c x f(n) ≤ g(n) ≤ d x f(n)을 만족하는 양의 실수 c,d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

 

Θ(n) = O(f(n)) ∩ Ω(f(n)), 교집합

o(f(n)) - Small o

주어진 복잡도 함수 f(n)에 대해서, o(f(n))은 모든 양의 실수 c에 대해 n ≥ N을 만족하는 모든 n에 대해 g(n) ≤ c x f(n)을 만족하는 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

 

ex) 5n^2이 o(n^2)에 속할까??

5n^2 ≤ c x n^2

c=2일 경우 위 부등식을 만족하지 못하므로  5n^2은 o(n^2)에 속하지 않는다.

 

 

Properties of Order Functions

1. g(n) ∈ O(f(n)) iff f(n) ∈ Ω(g(n))

2. g(n) ∈ Θ(f(n)) iff f(n) ∈ Θ(g(n))

3. if b>1 and a>1, then log_a(n) ∈ Θ(log_b(n))

4. if b>a>0, then a^n ∈ o(b^n)

5. For all a >0  a^n ∈ o(n!)

6. Following ordering, where k>j>2, b>a>1

Θ(lg n)  Θ(n)  Θ(n lg n)  Θ(n^2)  Θ(n^3)  Θ(n^k)  Θ(a^n)  Θ(b^n)  Θ(n!)

 

++ iff(if and only if) 필요충분조건

참조

https://nolzaheo.tistory.com/2

https://somethoughts.tistory.com/19

https://nolzaheo.tistory.com/3