[contents]
- Introduction
- Mathematical Background
- Analyzing Algorithms and Problems
- Classifying Functions by Their Asymptotic Growth Rates
- Searching an Ordered Array
computer algorithm 이란?
- 컴퓨터를 이용하여 유한한 시간내에 문제를 풀기위한 자세한 단계
...?! 직독직해하니 조금 이상하긴 하다.. 의미는 비슷하니 pass~
문제 해결 단계
1. 문제정의
- input
- output
2. 전략
3. 알고리즘 서술
- input
- output
- step
4. 분석
- Correctness
- Time/Space efficiency
- Optimality : problem complexity -> 문제복잡도와 알고리즘 복잡도가 같은 경우, 그 알고리즘을 optimal algorithm이라고 함
5. 구현
6. 확인 & 검증
이제 예시를 통해 확인해보자!
[Example : Search in an unordered array]
1. 문제정의
- input : E를 n개의 entry를 가진 배열이라고 하자. 특정 순서가 없이 배열되어있다. E[0],...,E[n-1]
- output : 특정 key값인 k를 가지고 있는 index를 찾아라. 해당 key가 없다면 -1을 반환해라.
2. 전략
- k를 찾거나 더이상 index에 값이 없을 때까지 각각의 entry와 k를 비교해라.
- k가 배열에 없다면 -1을 반환해라.
3. 알고리즘 서술
- input : E,n,K, E는 n개의 entries를 가진 배열이고 K는 찾아야 할 item이다. simplicity를 위해 우리는 K와 E의 entries는 정수라고 가정한다.
- output : E에서 K의 위치 ans를 반환한다. K가 없다면 -1을 반환한다.
Algorithm : Step (Specification)
4. 분석
- Basic Operation : array의 요소와 k를 비교하는 연산. 즉 위 알고리즘에서 K == E[index] 부분을 의미.
- Worst-Case Analysis
- W(n)는 input size n에 의해 수행되는 basic operation의 최대수이다.
- 위 예시에서 W(n) = n 이다.
- Worst case는 K가 배열의 마지막 위치에 존재하거나 K가 존재하지 않을 때 발생한다.
more analysis...
- Average-Behavior Analysis
- Optimality
- Correctness
[실험적 분석의 한계]
- 알고리즘 구현 필수적
- 실험에 포함되지 않는 input에 대한 수행시간 알 수 없음
- 임의의 알고리즘 2개를 비교하기 위해 software,hardware 사양이 같아야함
[이론적 분석의 장점]
- 구현하지 않아도 슈도코드로 표현가능(상위레벨에서 표현가능)
- 수행시간을 Input size n에 대하여 정의가능
- 모든 가능한 input에 대하여 고려 가능
- software/hardware 환경에 독립적으로 알고리즘 성능 측정가능
[Mathematical Background]
series 란 sequence의 합이다.
Arithmetic series
- 연속적인 정수들의 합
Polynomial Series
- 제곱수의 합
2의 제곱
교수님이 공식유도하는 법은 알아야 한다고 하셨다...
Arithmetic-Geometric Series
Analysis Tool : Logic
Proof
- Counterexample : 반례
- Contraposition : 대우 : p->q 와 ~q ->~p는 대우관계이다.
- Contradiction : 모순(귀류)
- Mathematical Induction : 수학적 귀납법
[Analyzing Algorithms and Problems]
- Correctness
- Amount of work done, and space used : 시간,공간복잡도
- Optimality, Simplicity
Correctness 는 증명될 수 있다.
하나의 알고리즘은 input(precondition)에서 output(postcondition)으로 변환되기 위한 step(operation,instruction,statement)의 연속으로 구성되어있다.
->알고리즘이 종료될 때, precondition을 만족하고 postcondition이 true라면 증명된다.
*Loop Invarient : 루프 불변성 -> 수학적 귀납법과 유사 (이후 자세히 살펴보기로 함)
Amount of Work Done
- 알고리즘의 효율성을 의미
- computer, 프로그래밍 언어, 프로그래머, 구현세부사항과 독립적으로 측정가능
- 보통 input size에 의존한다.
Basic Operation
- 문제의 기본 연산
- 수행되는 연산의 총합은 basic operation의 수에 비례한다.
Worst-Case Complexity
Dn : size가 n인 모든 가능한 input들의 집합
I : Dn의 element
t(I) : 수행되는 basic operation의 수
함수 W를 아래와 같이 정의한다.
W(n)은 어떠한 input size n에 대한 알고리즘에 의해 수행되는 basic operation의 최대수 이다.
W(n)은 worst-case complexity라고 부른다.
Average Complexity
worst case와 best case의 산술적 평균시간이 아닌, 다양한 data에 대한 평균 시간
Pr(I)를 input I가 발생할 수 있는 probability라고 하자.
이 때, 알고리즘의 평균시간은
우리는 알고리즘을 분석함으로써 t(I)를 결정한다.
하지만 Pr(l)은 분석적으로 계산될 수 없다.
예시를 들어 이해해보자!
Space Usage and Simplicity
Space usage
- time과 space는 tradeoff관계이다.
알고리즘에서 Simplicity는
- correctness에 대한 증명을 더 쉽게할 수 있다.
- 프로그램의 작성,디버깅,수정이 더 쉽다.
Optimality
각각의 problem은 complexity가 존재하는데, 최소 basic operation의 수가 존재한다.
problem의 complexity를 분석하기 위해
- 실제로 문제해결하려면 얼마나 많은 basic operation이 필요한지 묻는다.
Optimal 이란 "가장 잘 알려진 - the best known"이 아닌 "the best possible"을 의미한다.
An Algorithm이 optimal이라는 것을 보이는 법!
->해당 알고리즘을 분석하고 worst-case complexity WA(n)을 찾아라!!
어떤 함수 F에서 input size n을 가리즌 알고리즘은 최소 F(n)번의 step을 수행한다.
만약 WA(n) = F(n) 이면
그 알고리즘은 optimal 하다고 한다.
그렇지 않으면
there may be a
- better algorithm (=upper bound)
- better lower bound (문제복잡도)