[Algorithm] 분석 종류, 설계 기법, 표기법

■ 알고리즘의 조건

조건	설명
입력	0개 이상의 데이터 입력이 있어야한다.
출력	적어도 하나 이상의 결과를 출력해야한다.
명확성	각 단계와 명령은 모호하지 않고 명확해야한다.
유한성	유한한 단계를 거친 후, 반드시 종료해야한다.
유효성	각 명령어들은 실행 가능해야 한다.

 

■ 알고리즘의 표현 방법

1. 자연어

2. 순서도 (Flow Chart)

3. 의사코드 (Pseudo Code)

4. 프로그래밍 언어 (C, C#, C++ ...etc)

 

■ 알고리즘 분석 종류

종류	설명
최악의 경우를 분석 (★★)	어떤 입력이 주어지더라도 알고리즘의 수행 시간이 이 이상은 넘지 않는다는 '상한(Upper-Bound)'의 의미. * 수행시간이 가장 늦은 경우를 뜻함
평균의 경우를 분석	입력의 확률 분포를 가정하여 분석. 일반적으로 균등분포(Uniform Distribution)를 가정 * 수행시간이 평균적인 경우를 분석함
최선의 경우 분석	수행 시간이 가장 빠른 경우를 분석 * 최적(Optimal) 알고리즘을 찾는데 활용
일반적으로 알고리즘의 수행 시간은 '최악의 경우 분석'을 가장 널리 사용하며 최악의 경우는 계산하기 쉽고 응용에따라서 중요한 의미를 갖는다. ▼ (예) 등교시간 분석: 집을 나와서 지하철역까지 5분, 지하철로 학교까지 20분, 강의실까지 걸어서 10분 - 최선의 경우 : 5분 + 20분 + 10분 = 35분 - 최악의 경우 : 5분 + 20분 + 10분 + 지하철 기다리는 시간 10분 = 45분 - 평균의 경우 : 최선과 최악의 중간 = 40분

 

알고리즘을 설계한 뒤에는 알고리즘이 '자원'을 얼마나 소모하는지 분석해야함. 여기서 자원이란 소요시간, 메모리, 통신 대역 등을 의미함.

 

* 효율적인 알고리즘은 전체 실행시간이 짧으면서 메모리와 같은 컴퓨터 자원을 적게 사용하는 알고리즘임.

요즈음 알고리즘의 실행 시간을 효율적인 알고리즘의 기준으로 삼음

 

■ 성능 평가 기준

종류	설명
정확성	정확하게 동작하는가
작업량	얼마나 적은 연산을 수행하는가
메모리	얼마나 적은 메모리를 사용하는가
단순성	얼마나 단순한가
최적성	더이상 개선할 여지가 없을 만큼 최적화 되어있는가
* 알고리즘 수행 시간으로써 활용될만한 적절한 후보는 '작업량'이다. - 최악의 경우 (★) : 어떤 경우에도 이만큼의 성능은 보장해준다 - 평균의 경우 : 대체적으로 알고리즘이 내는 성능 - 최선의 경우 : 운이 좋다면 알고리즘은 이 정도의 성능을 낼 수 있다. (도움이 안됨)

 

■ 대표적인 알고리즘 설계 기법

기법	설명
분할 정복 (Divide and Conquer)	· 해결하려는 문제를 크기가 작은 여러 개의 부분 문제로 분할하여 해결 · 그 해답들을 통합하여 본래의 문제를 해결함 ·  분할 (divide) -> 정복 (conquer) -> 결합 (combine) 과정을 거침
동적 프로그래밍 [동적 궤법] (dp; Dynamic Programming)	· 문제를 여러 개의 하위 문제로 나누어 푼 다음 결합하여 최종적인 목적에 도달하는 것 · 동적 프로그래밍은 분할 정복과 유사 * 동적프로그래밍과 다른점?  : dp의 부분 문제들은 서로 의존성을 갖지만, 분할 정복의 하위 문제들은 서로 독립적이다.
그리디 알고리즘 (Greedy Algorithm)	· 선택해야할 방법이 여러 가지일 때 현재 상황에서 가장 최선인 것을 먼저 선택하는 기법 · 그 순간에 최적이라고 생각되는 것을 선택하는 방식임 · 언제나 최적해를 구한다는 보장은 없음
백트래킹 (Backtracking)	· 우선 하나의 가정에 대한 가능성을 확인해보고 가능하지 않다면, 다른 가정을 확인하는 것 · 알고리즘 구조 특성상 재귀 함수를 사용하여 구현됨
* 왜 효율적인 알고리즘이 중요한가? 1. 10억개의 숫자를 정렬하는데 PC에서 O(n^2) 알고리즘은 300여 년이 걸리는 반면에 O(nlogn) 알고리즘은 5분만에 정렬한다. 2. 효율적인 알고리즘은 슈퍼 컴퓨터보다 더 큰 가치가 있다.

 

■ 점근적 분석 (Asymptotic Analysis)

알고리즘이 주어진 데이터의 크기에 따라 수행 시간이나 사용 공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시한다.

 

소규모의 데이터 크기에선 알고리즘의 성능의 우수성을 가르기가 힘들 뿐더러 효율성이 크게 중요하지 않지만 입력 크기가 충분히 큰 문제에서는 비효율적인 알고리즘은 치명적이다.

 

수행 시간은 알고리즘이 수행하는 기본 연산 횟수를 입력크기에 대한 함수로 표현하고 이러한 함수는 다항식으로 표현되며 이를 입력 크기에 대한 함수로 표현하기 위해 점근적 표기법 (Asymptotic Notation)을 사용한다.

 

[점근적 분석법을 표기하는 방법 세 가지]

종류	설명
O(빅-오) 표기법	· 최악의 경우의 알고리즘 수행 시간을 나타냄. · 최악의 경우에도 성능을 보장하기 때문에 가장 많이 사용하는 표기법임 (점근적 상한법 [Upper Bound]) [특징] 1. 실행 시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시하여 사용 2. n이 무한대로 갈 때를 기준으로 평가하며 입력 데이터가 최악일 때 알고리즘이 보이는 효율을 기준으로 함 (ex) 데이터의 크기 n에 대한 최대 수행 시간이 2n^2+4n인 알고리즘은 O(n^2)으로 표기 * 입력값 n에 따른 알고리즘 수행 시간 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) * 이름 O(1) : 상수 시간 O(logn) : 로그 시간 O(n) : 선형 시간 O(nlogn) : 로그 선형 시간 O(n^2) : 제곱 시간 O(n^3) : 세제곱 시간 O(2^n) : 지수 시간
Ω(빅-오메가) 표기법	· 빅오 표기법과 반대. 점근적 하한선 (Lower Bound) · 주어진 알고리즘이 아무리 좋아도 빅오메가 표기의 함수보다는 나쁘며 시간이 더 걸린다는 의미. · 알고리즘 수행시간의 하한으로 "최소한 이 정도의 시간은 필요하다."라는 의미임 (ex. 이 함수는 아무리 빨라도 20분은 걸려요)
Θ(빅-세타) 표기법	· 점근적 상한선과 점근적 하한선의 교집합. * 주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위 안에 있다는 뜻임. (ex. 이 함수는 30분에서 1시간 정도 걸려요)

 

■ 공간복잡도

공간복잡도 = 고정 공간 + 가변 공간

(1) 고정 공간
: 프로그램의 크기나 입출력의 횟수와 관계없이 고정적으로 필요한 저장 공간
(ex. 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수(struct), 상수 등)

(2) 가변 공간
: 실행 과정에서 자료구조와 변수들이 필요로 하는 저장 공간
(ex. 함수가 순환 호출을 할 경우 요구되는 추가 공간이나 동적으로 필요한 공간)

 

■ 시간복잡도

시간 복잡도 = 컴파일 시간 + 수행 시간

(1) 컴파일 시간 : 프로그램마다 거의 고정적인 시간이 소요됨
(2) 수행 시간 
- 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행 시간보다 명령문의 실행 빈도 수에 따라 계산
- 알고리즘의 실행 시간을 좌우하는 기준으로는 for 루프의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출 횟수 등 시간 복잡도는 연산의 횟수를 셈

 

* 연산 횟수를 시간 복잡도로 계산할 경우의 장점

- 실행이 필요하지 않음 (코딩이 필요 없음)
- 하드웨어, 소프트웨어가 필요하지 않음 (의사코드로 충분히 계산할 수 있음)
- 모든 플랫폼에서 동일한 결과를 산출함

 

 

■ 점화식

 

* 점화 관계 (Recurrence Relation)

: 어떤 함수를 자신과 똑같은 함수를 이용하여 나타내는 것

* 점화식

어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

수열은 요소들을 일정한 순서로 나열한 형태로 표현하는데 이러한 요소들 사이에는 일정한 규칙이 있을 수 있고 요소들의 나열 대신
이 규칙으로 표현하는 것도 점화식이라고 함. 수열에서 n번째 항을 a0, a1, a2, a3...로 나타낸 식

[예]

an = an-1 + 2

f(n) = nf(n-1)

* 점화식은 자기 호출을 사용하는 재귀 함수의 복잡도를 구하는데 유용함
* 재귀적 관계를 이용하여 알고리즘의 수행 시간을 점화식으로 표현 가능