[알고리즘] 알고리즘 분석
알고리즘이란?
정의: 어떤 문제를 풀기 위한 유한 절차와 방법
- 여기서 문제는 '수학적으로' 정의된 문제들을 말한다.
- 입력값들이 주어졌을 때, 수학적으로 답(출력값)을 출하는 절차와 방법이다.
- 그렇기에 같은 문제에 대해 여러가지 알고리즘이 사용될 수 있다.
절차와 방법
- 계산 문제를 풀기위해서는 숫자와 사칙연산을 이용한다.
- 컴퓨터로 계산 문제를 풀기위해서는 컴퓨터에 주어진 명령어 집합을 이용해야한다.
알고리즘 분석
알고리즘 분석에는 2가지가 존재한다.
1. 실험적 분석(Experimental analysis)
정의
- 주어진 알고리즘 소스코드를 구현한 후 실행 했을 때의 시간을 측정한 것을 말
문제점
- 알고리즘을 실제 구현하기까지 시간이 걸림
- 두 알고리즘의 성능을 비교할 때 다양한 외부요인으로 정확히 판단하기 힘듬
2. 이론적 분석(Theoretical analysis)
정의
- 실제 구현이 아닌 이론적으로 알고리즘 수행시간을 기술하는 방법
- 시간은 주로 입력 값(보통 n으로 표기)에 관한 함수로 표현
- 다양한 외부요인과 무관하게 알고리즘 성능 표현 가능
- 이론적 분석을 통한 알고리즘 수행 시간을 시간 복잡도(time complexity)라고 한다.
빅-오(Big-Oh ) 표기법
- 이론적 분석에 걸리는 시간을 표현한 함수 자체보다 입력 사이즈에 대한 함수값이 얼마나 빠르게 증가하는지 더 중요
f(n)와 g(n)를 자연수에서 실수로의 함수라고 하자.
이 때 n > n0에 대하여
f(n) ≤ c ●g(n)
를 만족하 어떤 실수 c >0와 자연수 n0 > 0이 존재하면
f(n) = O(g(n)) 이라고 한다.
수학적 기호를 이용한 정의 :
∃ c,n0 > 0 이면 ∀n > n0, f(n) ≤ c ●g(n)
예시 문제 1)
알고리즘 비교
두 알고리즘의 수행 시간을 이론적으로 비교하는 방법
1. 두 알고리즘의 수행하는데 필요한 기본 연산의 횟수를 함수로 표
2. 1번의 함수를 Big -Oh 표기법으로 표현
3. Big- Oh 표기법 안의 두 함수를 비교하여, 더 느리게 증가하는 함수로 표현되는 알고리즘이 이론적으로 더 빠른 알고리즘
빅-오메가(Big-Omega) 표기법
어떤 두 함수 f(n), g(n) 에 대하여 f(n) =O(g(n)) 를 만족하면 g(n) = Ω(f(n))이다.
수학적 기호를 이용한 정의:
∃ c,n0 > 0 이면 ∀n > n0, g(n) ≤ c ●f(n)
빅-세타(Big-Theta)표기법
f(n) = O(g(n)) 임과 동시에 g(n) = O(f(n)) 이면 f = ϴ(g(n)) and g = ϴ(f(n)) 이다.
수학적 기호를 이용한 정의
∃ c1 , c2 , n0 > 0 이면 ∀n > n0 , c1·f(n) ≤ g(n) ≤ c2·f(n)
실습문제
1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both( in which case f = ϴ(g) )
(A) f(n) = n - 100, g(n) = n - 200
풀이:
정답: f = ϴ(g) 성립
(B) f(n) = n**1.01, g(n) = n(logn**2)
풀이:
정답: f = Ω(g) 만 성립
2. 문제
풀이:
혹시 틀린 부분 있으면 알려주시면 감사하겠습니다.
틀린 부분 있어도 너그럽게 봐주시고 피드백 부탁드리겠습니다.
