알고리즘의 점근적 분석이란?
크기가 작은 문제에서는 알고리즘의 효율성이 중요하지 않다. 그래서 비효율적인 알고리즘을 사용해도 무방하다. (오히려 더 빠른 경우도 존재한다)
크기가 충분히 큰 문제에서는 알고리즘의 효율성이 매우 중요하다. 그래서 비효율적인 알고리즘은 치명적으로 작용한다.
이렇게 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다. 표기법에는 Ο, Ω, Θ, ω, ο 가 존재한다.
점근적 상한 ( asymptotic upper bound )
정의
(lim n->INF) f(n) / g(n) <= c
O( g(n) ) 의 의미는 g(n)의 비율로 증가하는 함수를 뜻한다.
Formal definition
O(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) }
f(n) ∈ O(g(n))을 관행적으로 f(n) = O(g(n))이라고 쓴다.
직관적 의미
f(n) = O(g(n)) ⇒ f 는 g보다 빠르게 증가하지 않으며 상수 비율의 차이는 무시한다.
알 수 있는 한 최대한 엄밀하게 작성하기
nlogn + 5n = O(nlogn) 인데 굳이 O(n2)으로 쓸 필요는 없다. 엄밀하지 않은 만큼 정보의 손실이 일어나기 때문이다.
예시
f(n) = 3n^2 + 2n
점근적 상한 O(n^2) 등
f(n) = 7n^2 – 100n
점근적 상한 O(n^2) 등
f(n) = nlogn + 5n
점근적 상한 O(n^2), O(nlogn) 등
f(n) = 3n
점근적 상한 O(n^2), O(n) 등
f(n)= 5000n+1000
점근적 상한 O(2/3 * n), O(0.001 * n^2) 등
f(n)= 300n^2+10^9
점근적 상한 O(n^2 - 8), O(1/50*n^2) 등
예상 문제
Algorithm(A[], n) {
sum1 <- 0
for i <- 1 to n
sum1 <- sum1 + A[i]
sum2 <- 0
for i <- 1 to n
for j <- 1 to n
sum2 <- sum2 + A[i] * A[j]
return sum1 + sum2
}
더보기
알고리즘의 총 연산횟수
4n^2 + 4n +4
증명
f(n) = 4n^2 + 4n +4이면 O(n^2)이다. 왜냐하면 n_0가 10, c=100일 때 n > 10에 대하여 f(n) <= 100*(n^2)이기 때문이다.
Algorithm(A[][], B[][], M[][], n) {
for i <- 1 to n
for j <- 1 to n {
M[i, j] <- 0
for k <- 1 to n
M[i, j] <- M[i, j] + A[i, k] * B[k, j]
}
}
더보기
알고리즘의 총 연산횟수
4n^3 + 2n^2 + n + 1
증명
f(n) = 4n^3 + 2n^2 + n + 1이면 O(n^3)이다. 왜냐하면 n0가 10, c=100일 때 n > 10에 대하여 f(n) <= 100*(n^3)이기 때문이다.
Algorithm(A,n) {
tmp ← A[0];
for i←1 to n-1 do
if tmp < A[i] then
tmp ← A[i]
return tmp
}
더보기
알고리즘의 총 연산횟수
3n - 1
증명
f(n) = 3n-1이면 O(n)이다. 왜냐하면 n_0가 100, c=100일 때 n >= 100에 대하여 f(n) <= 100n이기 때문이다.
점근적 하한 (asymptotic lower bound)
정의
(lim n->INF) f(n) / g(n) >= c
Ω( g(n) ) 의 의미는 적어도 g(n)의 비율로 증가하는 함수를 의미한다.
O( g(n) )과 대칭적이다.
Formal definition
Ω(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n)≤f(n) }
직관적 의미
f(n) = Ω(g(n)) ⇒ f는 g보다 느리게 증가하지 않는다
예시
f(n)= 10^(-9) * n^2 - 200
점근적 하한 Ω(500), Ω(3000n), Ω(n^2) 등
f(n)= 0.0001 * 2^n -10^9
점근적 하한 Ω(1), Ω(20), Ω(2000n), Ω(100 * 2^n) 등
점근적 동등 (asymptotic tight bound)
정의
어떤 양수 n0와 c1, c2가 존재하고 n ≥ n_0일 때 항상 c_1g(n) ≤ f(n) ≤ c_2g(n)이 성립한다.
Θ( g(n) ) 의 의미는 g(n)의 비율로 증가하는 함수를 의미한다.
Formal definition
Θ( g(n) ) = O( g(n) ) ∩ Ω( g(n) )
직관적 의미
f(n) = Θ(g(n)) ⇒ f는 g와 같은 정도로 증가한다
예시
f(n)= log n + n^2 + 200
점근적 동등 Θ(n^2) 등
f(n)= 3^n +n^3+n^2+2
점근적 동등 Θ(3^n) 등
예상 문제
f(n)=2n^2-10n+3이 Θ(n^2)임을 증명하시오.
더보기
증명
f(n)=2n^2-10n+3이면
n_0=10^10이고 c_1=10^-100이고 c_2=1000이면 n>=10^10일 때,
10^-100 * Θ(n^2) <= 2n^2-10n+3 <= 1000 * Θ(n^2)이 성립한다.
저장/검색의 시간 복잡도
배열
O(n)
Binary search trees
최악의 경우 Θ(n)
평균 Θ(log n)
Balanced binary search trees
최악의 경우 Θ(log n)
B-trees
최악의 경우 Θ(log n)
Hash table
평균 Θ(1)