[자료구조] 1-2. [순환 알고리즘과 시간복잡도]

알고리즘의 성능 분석 기법

실행시간을 측정하는 방법

• 두 개의 알고리즘 실제 실행 시간을 측정하는 것
• 실제로 구현하는 것이 필요
• 동일한 하드웨어를 사용해야 함

알고리즘의 복잡도를 분석하는 방법(이론적)

• 직접 구현하지 않고 수행시간을 분석하는 것
• 알고리즘이 수행하는 연산 횟수를 측정하여 비교
• 일반적으로 연산의 횟수는 n의 함수
• 시간 복잡도 분석: 수행시간 분석
• 공간 복잡도 분석: 수행시 필요한 메모리 공간 분석

파이썬의 실행시간 측정 코드 예

import time

myBag = []
start = time.time
insert(myBag, '축구공')
...
end = time.time()
print("실행시간 =", end-start)

복잡도 분석

시간 복잡도

• 산술, 대입, 비교, 이동의 기본적인 연산 고려
• 알고리즘 수행에 필요한 연선 개수를 계산
• 입력 개수 n에 대한 함수 → 시간 복잡도 함수, T(n)

예) Bag의 삽입 연산

#리스트 맨 뒤에 삽입
#append() 함수 사용

def insert(bag, e):   # bag에 항목 e를 넣음
    bag.append(e)       # 파이썬 리스트 맨 뒤에 추가

# 효율적(바로 삽입 가능)

#리스트 맨 앞에 삽입
#insert() 함수 사용

def insert(bag, e):   #bag에 항목 e를 넣음
    bag.insert(0, e)    #파이썬 리스트 맨 앞에 추가

#비효율적(가방 모든 물건을 먼저 이동해야 삽입 가능)

n^2를 구하는 문제

알고리즘	A	B	C
유사 코드	sum ← n*n	for i← 1 to n do
sum ← sum + n	for i←1 to n do
for j← 1 to n do
sum← sum + 1
연산 횟수	대입연산: 1
곱셈연산: 1	대입연산: n+1
덧셈연산: n	대입연산: n^2+n+1
덧셈연산: n^2
복잡도 함수	Ta(n)=2	Tb(n)=2n+1	Tc(n)=2n^2+n+1

빅오 표기법

• 차수가 큰 항이 절대적인 영향
• 다른 항들은 상대적으로 무시

예) T(n) = 2^2 + n+ 1

• n=1일 때: T(n) = 1+1+1 = 3 (n^2항이 33.3%)
• n=10일 때: T(n) = 100 + 10+ 1 = 111 (n^2항이 90%)
• n=100일 때: T(n) = 1000 = 100 + 1 = 10101(n^2항이 99%)
• n=1000일 때: T(n) = 1000000 + 1000 + 1 = 1001001(n^2항이 99.9%)

두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n0 에 대해 |f(n)|≤c|g(n)|을 만족하는 상수 C와 n0가 존재하면 f(n) = O(g(n))임

(연산의 횟수를 대략적[점근적]으로 표기한 것)

최선, 평균, 최악의 경우

최선의 경우

• 수행 시간이 가장 빠른 경우
• 의미 없는 경우가 많음

평균의 경우

• 수행시간이 평균적인 경우
• 계산하기 어려움

최악의 경우

• 수행 시간이 가장 늦은 경우
• 가장 널리 사용되며, 계산하기 쉽고 응용에 따라서 중요한 의미를 가짐
• 예) 비행기 관제업무, 게임, 로보틱스

순환 알고리즘

• 알고리즘이나 함수가 수행 도중 자신을 다시 호출하여 문제를 해결하는 기법
• 정의자체가 순환적으로 되어 있는 경우 적합
• 팩토리얼 구하기 $n!=\begin{cases}1, n=1\n*(n-1)!, n>1\end{cases}$
• 피보나치 수열 $fib(n)=\begin{cases}
  0,if\ \ \ n=0\
  1,if\ \ \ n=1\
  fib(n-2)+fib(n-1)\ \ \ otherwise
  \end{cases}$
  (이항계수, 하노이의 탑, 이진탐색 등 )