알고리즘 성능평가

 

 

 

 

 

• 복잡도 
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
    
    
• 빅오표기법(Big-O Notation)
  수학적 정의는 모든 $ 0 < n_{0} \leq n $에 대하여 $ 0 \leq f(n) \leq k \bullet g(n) $인 양의 상수 $ k $와 $ n_{0} $가 존재하면 $ f(n) = O(g(n)) $이다.
  쉽게 말하면 어떤 프로그램을 실행했을 때 연산횟수가 $ 2n^2 + 5n + 1000 $이라고 하면 이 프로그램의 시간복잡도를 계수를 제외한 최고차항만 남겨서 $ O(n^2) $이라고 하는 것이다. 이렇게 표기하는 이유는 $ n $의 값이 무한히 커지면 최고차항을 제외한 항들은 최고차항에 비해 값이 너무 작아 의미가 없기 때문이다.
  
  
• 빅오 표기법 성능비교
  왼쪽 부터 상수 시간, 로그 시간, 선형 시간, 로그 선형 시간, 이차 시간, 삼차 시간, 지수 시간이라 하며 오른쪽으로 갈수록 시간이 오래걸리고 성능이 안 좋은 알고리즘이다.
  $ O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^n) $
  
  
• 빅오 표기법 예제
  
  

s = 0
for i in range(1, 10):
	s += i
print(i)

위와 같은 단일 반복문 프로그램은 데이터를 하나씩 확인하며 합계를 계산하므로 데이터의 개수 N에 비례하여 수행 시간이 늘어나므로 시간 복잡도는 $ O(N) $이다.

for i in range(1, 10):
	for j in range(1, 10):
    	print('i*j:', i*j)

위와 같은 이중 반복문 프로그램은 데이터를 한번 확인한 상태에서 한번 더 확인해야하므로 시간 복잡도는 $ O(N^2) $이다.

$ O(1) $: 스택에서 Push, Pop을 하는 경우

$ O(logN) $: 이진트리

$ O(N) $: 단일 반복문

$ O(NlogN) $: 퀵 정렬, 병합정렬, 힙 정렬

$ O(n^2) $: 이중 반복문, 삽입정렬, 거품정렬, 선택정렬

$ O(2^n) $: 피보나치 수열

 

• 수행 시간 구하기

import time 
start_time = time.time() # 측정 시작
s = 0
for i in range(1, 1000001):
	s += i
print(s)
end_time = time.time() # 측정 종료
print('수행시간:', end_time - start_time)

실행 결과

위와 같은 방법으로 프로그램 코드의 전후로 time()을 이용하여 수행시간을 구할 수 있다.