알고리즘 개요

알고리즘이란 무엇인가?

알고리즘(Algorithm)의 정의

 - 주어진 문제를 해결하기 위해 잘 정의된 동작들의 유한 집합

 

자료구조

 - 알고리즘의 객체
 - 구조화되고 조직화된 자료의 저장/추출/관리 방법
 - 추상데이터타입 (Abstracted Data Type)
 - 배열, 스택, 큐, 트리....

 

알고리즘 선택 시 주의사항

 - 하나의 문제에 대해 여러 알고리즘이 존재
 - 절대적인 최상의 알고리즘은 없다.
 - 주어진 문제와 환경을 먼저 숙지하라.
 - 속도와 자원(resource)의 상관관계
 - 단순한 알고리즘이 좋다.
  . 지나친 속도결벽증은 금물
  . 알고리즘의 사용빈도에 따른 선택

 

경험적 분석과 수학적 분석

- 분석은 알고리즘을 정확히 선택하기 위한 방법

- 시간 소요량 vs 공간 소요량

 

1) 경험적 분석(Empirical analysis)

 . 실제 코드를 작성 후, 실행하여 시간을 측정

 . 데이타 수를 다르게 하여 함수관계 유추

ex) 선택 정렬일 경우 N의 수가 늘어날 수록 비효율적이다.

N 의 수	100	500	1000	2000	5000
선택정렬 결과 시간	2	47	186	736	4578

 

2) 수학적 분석 (Mathematical Analysis)

 . 알고리즘 자체를 가지고 수학적인 분석을 함

Ex)
T(N) = c1 + (c1 + c2) + (c1 + c2*2) ... + (c1 + 2*(N-1))
= c1*N + c2*(1+2+.... + N-1)
= c1*N + c2*((N-1)*(N)/2)
= 0.5 * c2 * N * N + (c1 -0.5 * c2) * N

 

최악의 경우와 최선의 경우

- 최악의 경우 (Worst Case) : 가장 많은 시간과 자원을 필요로 하는 경우

- 최선의 경우 (Best Case) : 가장 적은 시간과 자원만이 소요되는 경우

- 평균의 경우 (Average Case)

 . 개념이 모호함 자료의 균일분포? 가장 많은 빈도의 경우 ?

=> 가장 유용하게 쓰이는 경우는 '최악의 경우' 를 알고 개선하는 경우가 많다.

 

(성능 표현의) 알고리즘의 유형

- 상수 : 입력자료수와 관계없이 일정한 실행시간 ex) 해쉬 검색 알고리즘 등

- logN

 L Divide & conquer 방법 사용시

 L 이진 검색, 이진트리 검색 등

- N : Scan 방법 사용시, 선형 검색 등

- N log N :  Divide & conquer & Merge 방법 사용시, 병합 정렬 등

- N² : 이중 루프, N³ : 3중 루프

​=> 위에서부터 아래로 갈 수록 자료수가 증가함에 따라 실행시간이 증가한다.

 

 

대표적인 표기법이 3가지

- 알고리즘의 성능을 객관적으로 표현하는 방법

 

- O 표기법 (Big-Oh Notation)

 : 실행시간 함수 T(N)이 N₀ 보다 큰 N에 대하여 항상 C₀f(N)보다 작거나 같은 C₀와 N₀가 존재한다면 T(N)은 O(f(N)) 이라고 한다. 즉  N >= N₀인모든 N에 대하여 T(N) <= C₀f(N)이 만족하면 T(N) = O(f(N)) 이다.

 : 보통 T(N)에서 가장 영향력있는 항이 선택된다.

Ex) T(N) = 3N² + 1 이라면 O(N²)
. N >=1 인 모든 N에 대해 T(N) <= 4N² 만족,
L C₀f(N) = 4N²

- Ω(오메가) 표기법 : 실행시간 함수 T(N)이 N₀보다 큰 N에 대하여 항상 C₀f(N)보다 크거나 같은 C₀와 N₀가 존재한다면 T(N)은 Ω(f(N)) 이라고 한다. 즉 N>=N₀ 인 모든 N에 대하여 T(N)>=C₀f(N)이 만족하면 T(N)=Ω(f(N))이다.

 

- θ(세타) 표기법 : 실행시간 함수 T(N)이 N₀보다 큰 N에 대하여 항상 C₁f(N)보다 크거나 같고 C₂f(N)보다 작거나 같은 C₁, C₂가 존재한다면, T(N)은 θ(f(N)) 이라고 한다. 즉 N>=N₀ 인 모든 N에 대하여 C₁1f(N) <= T(N) <=C₂f(N)이 만족하면 T(N)=θ(f(N))이다.