[알고리즘] 알고리즘 표현 방법과 분석, 복잡도
알고리즘 표현 방법
알고리즘의 표현방법 및 종류
자연어(natural language)
순서도(flow chart)
가상코드(pseudo code)
프로그래밍 언어(program language)
알고리즘의 표현 방법
자연어 기술 방법
일상적으로 사용하는 말이나 글로 이용하는 방법, 말과 글이 지니는 모호성때문에 알고리즘의 명확성을 지키지못할 가능성 존재
순서도표현 방법
순서도(Flowchart)나 NS(Nassi-Shneiderman)차트와 같은 그래픽적인 표현 방법
표현방법이 복잡하고 대규모의 알고리즘을 표현하기 힘든 문제점, 읽기/변경하기 곤란
의사코드(Pseudo Code)기술 방법
자연어 기술 방법을 보다 간단화 한 것으로 알고리즘을 프로그래밍 언어와 유사한 형태로 풀어 써 놓은 것, 특정한 문법이 없음
알고리즘 분석 기준
프로그램의 성능을 평가하는 측정 기준은 알고리즘의 수행시간과 명령어의 실행 빈도수, 기억 공간 등이 사용
알고리즘 분석 단계
1단계
알고리즘에 입력될 데이터의 특성을 결정
메모리 요구사항이나 필요조건에 대하여 평균적인 수행시간(run time)을 얻을 수 있는 입력데이터를 정한다.
2단계
수행시간에 직접적으로 영향을 미치는 연산들을 분리하여 기본적인 연산을 결정
3단계
기본적인 연산들의 각 연산횟수에 대하여 평균의 경우와 최악의 경우에 대한 수학적 분석을 수행
알고리즘 복잡도
점근적 분석(Asymptotic Analysis)
입력의 크기가 충분히 큰 경우에 대한 분석
이미 알고 있는 점근적 개념의 예
lim f(n)
n -> ∞
Ο(빅오미크론), Ω(빅오메가), Θ(빅세타), ω(리틀오메가), ο(리틀오미크론) 표기법
점근적인 복잡도 평가 - 시간적 복잡도 평가
매개변수n
알고리즘에서 문제의 크기를 나타냄
처리할 자료항목의 수로서 수행시간에 가장 많은 영향을 끼침
e.g.) 다항식의 차수이거나 탐색이나 정렬될 파일의 크기, 그래프의 노드 수
점근적인 복잡도 평가 개요
알고리즘의 복잡도를 평가할 때 주요 항 이외의 항을 무시한다는 것은
n의 값이 무한에 가까워졌을 때, 복잡도가 어떻게 되느냐 하는 점에
주목하기 위한 것으로 이것을 점근적인 복잡도 평가라고 함
알고리즘을 분석할 때 주요 항 이외의 항과 주요항에 있는 계수도 무시하여
꼭 필요한 부분만으로 알고리즘의 복잡도를 표기하는 방법
공간 복잡도(space complexity)
프로그램을 실행시켜 완료하는데 소요되는 총 저장공간
Sp = Sc + Se
Sc : 고정 공간, 프로그램이 실행되는 데이터의 크기와 관계없이 일정한 공간
e.g.) 명령어 공간, 단순 변수, 복합 데이타 구조와 변수, 상수
Se : 가변 공간
크기가 변하는 데이타 구조와 변수들이 필요로 하는 저장 공간으로 필요 공간이 데이터의 개수에 따라 변함
데이터의 개수를 n이라고 하면 프로그램에 따라 2 x n, 3 x n, n x n의 영역이 필요
런타임 스택(runtime stack)을 위한 저장 공간
예제) n개의 데이터를 더하는 프로그램
float sum(float list[], int n){
float tempsum = 0;
int i;
for(i = 0; i < n; i++)
tempsum += list[i];
return tempsum;
}
list[], n, tempsum, i => n+3개의 데이터 공간
필요한 공간
프로그램 사이즈 = 고정
데이터 사이즈 = n + 3
시간 복잡도(time complexity)
프로그램을 실행시켜 완료하는데 걸리는 시간
Tp = Tc + Te
Tc : 컴파일 시간
Te : 실행 시간
단위 명령문 하나를 실행하는데 걸리는 시간
실행 빈도수(frequency count)
예제) 프로그램은 반복하여 수행되는 프로그램으로 수행 시간이 컴퓨터마다 다르므로 수행 시간에 대한 추정해 보면
- float sum(int n){
- int count = 0;
- int i;
- for(i = 0; i < n; i++)
- count += 2;
- count += 3;
- return count;
- }
n=0 일 경우 : for loop은 실행이 되지 않으므로 전체 실행되는 문장 4개 = 2번문, 4번문, 6번문, 7번문
n=0 이 아닐 경우 : 전체 실행되는 문장 2 x n + 4 개 = 2번문 + 4번문, 5번문을 n번 수행 + 4번문, 6번문, 7번문
점근적 복잡도의 예
정렬 알고리즘들의 복잡도 표현 예
- 선택 정렬
Θ( n2) - 힙정렬
O(nlogn) - 퀵정렬
O( n2) 평균Θ(nlogn) - 시간순: 힙정렬<퀵정렬<선택정렬
시간 복잡도 분석의 종류
Worst-case
Analysis for the worst-case input(s)
Average-case
Analysis for all inputs
More difficult to analyze
Best-case
Analysis for the best-case input(s)
별로 유용하지 않음
저장/검색의 복잡도
- 배열 O(n)
- Binary search trees
- 최악의 경우: Θ(n)
- 평균: Θ(log n)
- Balanced binary search trees
- 최악의 경우 : Θ(log n)
- B-trees
- 최악의 경우: Θ(log n)
- Hash table
- 평균 : Θ(1)
점근적 표기법(Asymptotic Notations)
O( g(n) ) (오크미론)
시간복잡도(시간복잡도에서최대상한값으로표기하는방법)
기껏해야g(n)의비율로증가하는함수 e.g., O(n), O(n log n), O(n2), O(2n), …
| 복잡도표기 | 설명 |
|---|---|
| O(1) | 상수형, 입력 크기와 무관하게 바로 해를 구함. 해쉬 |
| O(logN) | 로그형, 입력 자료를 나누어 그 중 하나만 처리 |
| O(N) | 선형, 입력 자료를 차례로 하나씩 모두 처리 |
| O(NlogN) | 분할과 합병형, 자료를 분할하여 각각 처리하고 합병 |
| O(N2) | 제곱형, 주요처리(기본연산) loop 구조가 2중인 경우 |
| O(N3) | 세제곱형, 주요처리(기본연산) loop 구조가 3중인 경우 |
| O(2n) | 지수형, 가능한 해결방법 모두를 다 검사하며 처리함 |
Formal definition (정의)
n0를 기준으로 n0보다 오른쪽에 있는 모든 n값에 대해 함수 f(n)은 함수 cg(n)보다 작거나 같다는 의미이다.
그래프가 아래에 있을 수록 수행시간이 짧은 것이므로 성능이 좋은 것이다.
f(n) ∈ O(g(n)을관행적으로f(n) = O(g(n))이라고쓴다.
직관적 의미
f(n) = O(g(n)) ⇒ f는 g보다 빠르게 증가하지 않는다
상수 비율의 차이는 무시
Ω( g(n) ) 오메가
적어도 g(n)의 비율로 증가하는 함수
O(g(n))과 대칭적
Formal definition (정의)
n0를 기준으로 n0보다 오른쪽에 있는 모든 n값에 대해 함수 f(n)은 함수 cg(n)보다 크거나 같다는 의미이다.
직관적 의미
f(n) = Ω(g(n)) ⇒ f는g보다느리게증가하지않는다
Θ( g(n) ) 세타
가율이 동일한 함수들의 집합
g(n)의비율로증가하는함수
Big O 표기법이 최대상한을 Ω 표기법이 최소하한을 표기하는 것과 달리 증가율이 동일한 함수들의 집합을 나타냄
Formal definition(정의)
n0를 기준으로 n0보다 오른쪽에 있는 모든 n값에 대해 함수 f(n)은 함수 c1g(n)보다 크거나 같거나 c2g(n)보다 작거나 같다는 의미이다.
직관적 의미
f(n) = Θ(g(n)) ⇒ f는 g와 같은 정도로 증가한다.
o(g(n))
g(n)보다 느린 비율로 증가하는 함수
𝜔( g(n) )
g(n)보다 빠른 비율로 증가하는 함수
Little o 표기법과 대응하는 의미
크기 n인 배열에서 원소 찾기
Sequential search
- 배열이 아무렇게나 저장되어 있을 때
- Worst case: Θ(n)
- Average case: Θ(n)
Binary search
- 배열이 정렬되어 있을 때
- Worst case: Θ(log n)
- Average case: Θ(log n)