입력과 출력으로 명시 가능한 문제에 대해 해결 절차를 체계적으로 기술한 것
문제를 해결하는 여러 알고리즘 중 어떤 것이 가장 좋은지 평가하기 위한 척도
1. 최악의 경우 수행시간
크기가 n인 모든 가능한 입력에 대해 기본연산 수의 최대값. W(n)으로 나타낸다.
수행 최대시간을 보장하지만, 정확한 수행시간을 제시하지 못한다. 알고리즘 수행시간 기본연산 수 분석은 보통 최악의 경우에 한다
2. 평균적인 경우 수행시간
크기가 n인 모든 가능한 입력에 대해 실행되는 기본연산 수의 평균. A(n)으로 나타낸다
최악의 경우 수행시간보다 실제 수행시간과 유사하지만, 분석이 어렵다
3. 최선의 경우 수행시간
크기가 n인 모든 가능한 입력에 대해 실행되는 기본연산 수의 최소값. B(n)으로 표기
예시 ) 배열에서 최대값 찾기
arrayMax(array, n):
m = list[0]
for i = 1 to n-1
if (m > array[i]) then m = list[i]
output m
시간복잡도 분석. n이 매우 커질 때 수행시간을 증가율에 의해 분석한다.
O(1) < O(logn) < O(sqrt(n)) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(a^n)로 자주 표기한다
1. Big-O (O(f(n))
실수 c와 음이 아닌 정수 n0에 대해 n >=n0인 모든 n에 대해 g(n) <= c f(n)을 만족하는 함수 g의 집합
g(n) ∈ O(f(n)). 함수 g는 함수 f보다 빠르게 증가하지 않는다. 기껏해야 f(n)의 비율로 증가하는 함수들이다. n이 커지면 상수는 의미가 없어져 무시한다
따라서 g(n)의 증가율이 logn이라도 O(n^2)에 속한다. 틀린 것이 아니라 정확성이 떨어질 뿐이다.
2. Big-Omega Ω(f(n))
실수 c와 음이 아닌 정수 n0에 대해 n >=n0인 모든 n에 대해 g(n) >= c f(n)을 만족하는 함수 g의 집합
3. Big-Theta Θ(f(n))
실수 c1, c2와 음이 아닌 정수 n0에 대해 n>= n0 일때 c1 f(n) <= g(n) <= c2 f(n)을 만족하는 세수 n0, c1, c2가 존재하면 g(n) ∈ Θ(f(n))이다
예시) n개 키를 가진 배열에서 주어진 키 찾기
index = 0
while (index < n and x != array[index]) do
index += 1
예시2) n이 소수인지 판별하기
i = 2
while (i*i <= n) do
if (n%i == 0) then
return True
i +=1
return False