What is Algorithm Complexity?
- 문제계산(computation)이 얼마나 어려운가를 나타내는 측정치이다.
- 계산을 위한 비용에 대한 측정치이다.
- 일반적인 복잡도 측정:
- 시간 복잡도: # 필요한 연산 or 단계들
- 공간 복잡도: # 필요한 메모리 비트수
Complexity Depends on Input
- 대부분의 알고리즘은 입력의 크기에 따라 복잡도가 달라진다.
- e.g., 당연하게도 길이가 긴 리스트가 짧은 리스트보다 탐색하는데 시간이 더 오래걸린다.
- 따라서, 복잡도는 입력의 크기/길이에 대한 함수로 표현한다.
- 복잡도를 나타내는 함수를 통상적으로 입력 크기가 최악인 경우를 고려한다.
Example: Max Algorithm (최댓값 구하기)
procedure max(a_1,a_2,⋯,a_n: integers)
v := a_1 {지금까지 가장큰 요소로 가정한 a_1}
for i:=2 to n {요소의 나머지들에 대해..}
if a_i > v then v := a_i {더 큰수를 찾았다면??}
{이 시점에서 변수v의 값은 리스트 중 가장큰 정수값일 것이다.}
return v- Problem: 최댓값 구하기 알고리즘(Max Algorithm)에서 최악의 시간복잡도의 exact order of growth (Θ)를 찾아라.
- 코드 각 라인을 하나의 수행으로 볼 때의 시간이 상수 시간을 갖는다고 가정해보라.
- Max Algorithm의 시간복잡도 분석
- 최악의 경우, 정확한 수행 시간이 어떻게 될까?
Example: Linear Search
procedure linear search
(x: 찾을 정수, a_1, a_2, ⋯, a_n : 서로 다른 정수)
i := 1 #t_1
while (i≤n ∧ x≠a_i) #t_2
i := i+1 #t_3
if i≤n then index := i #t_4
else index := 0 #t_5
return index #t_6
hello world :)