[Algorithm/알고리즘] Algorithm Analysis(알고리즘 분석)

Efficiency

▶ Predicting the resources that the algorithm requires

- Resources in terms of time: running time

- Resources in terms of space: memory usage

▶ Efficiency depends on input size

▶ Various ways of determining the size of input data

- Depends on the problem being studied

- Number of items in the input (e.g. sorting)

- Total number of bits (e.g. integer arithmetic)

▶ Must have a model of the implementation technology

 

 

Random Access Machine 

▶ Generic one-processor, random-access model of computation

▶ RAM contains instructions commonly found in real computers: arithmetic, control, data movement

▶ Each instruction takes a constant amount of time.

 

 

Runtime

먼저 삽입정렬의 수행시간을 살펴보자.

참고로 첫 번째 줄에서 n-1이 아니라 n인 이유는 마지막 n+1이 됐을 때 확인하는 단계까지 있기 때문이다.

n번째 라인을 실행하는 데 걸리는 시간이 ct라고 정의했다.

Running time은 n의 크기에 달려 있고, ti에 의해 결정된다.

 

Best case의 경우, 즉 이미 정렬되어 있다면?

ti = 1이므로 T(n) = an+b가 된다.

반면, Worst case의 경우, 즉 역순으로 정렬되어 있다면?

ti = i이므로 T(n) = an^2 + bn + c가 된다.

 

이처럼 같은 알고리즘도 최선, 최악의 경우에 따라 수행시간이 달라진다.

보통은 최악의 경우에 의거해 수행시간을 판별한다. 이유는 다음과 같다.

(1) Worst case running time provides an upper bound: Guarantee that algorithm will never take any longer

(2) For some algorithms, worst case occurs fairly often: e.g. searched element is not present

(3) Average case is often roughly as bad as worst case: e.g. insertion sort is still quadratic on average

 

또 이진탐색의 정렬시간은 어떨까?

데이터가 정렬되어 있지 않은 linear search의 경우, 최악 수행시간은 n이다.

반면, 데이터가 정렬되어 있는 binary search의 경우, 최악 수행시간은 log2_n이다.

 

 

Correctness

▶ Basic Considerations

- Automatic proof of correctness is not possible.

- There are practical techniques and rigorous formalisms that help to reason about the correctness of (parts of) algorithms.

 

▶ Partial VS Total

도통 이해가 안 가서 다음 글을 참고했다.

What is the correctness of an algorithm?

▶ Assertion: Statement about the state of execution -> to prove partial correctness one associates a number of assertions with specific checkpoints in teh algorithm

Preconditions: assertions that must be valid before the execution (input)

Postconditions: assertions that must be valid after the execution (output)

 

▶ Loop invariants: assertions that are valid any time they are reached

Initializtion: it is true before the first iteration

Maintenance: if it is true before an iteration then it is true after that iteration

Termination: when the loop terminates, it gives a useful property that helps to show that algorithm is correct

 

 

Asymptotic Complexity 복잡도의 점근적 표기

- To simplify the analysis of running time, getting rid of unnecessary details

- Big-O notation: asymptotic upper bound, used for worst-case analysis

- Big-Ω notation: asymptotic lower boudn, used for best-case analysis

- Big-Θ notation: asymptotic tight bound

 

예제. 다음 식의 점근적 복잡도는?

(1) 0.001*n^2 + 70000n = Θ(n^2)

(2) 2^n + n^10000 = Θ(2^n)

(3) n^k + c^n = Θ(c^n)

(4) logk_n+n^e = Θ(n^e)

(5) 2^n + 2^n/2 = Θ(2^n)

(6) n^logc + c^logn = Θ(c^logn)

(7) 2n^3 + 100n*logn + 5 = Θ(n^3)

(8) 30logn + log2^n = Θ(n)

(9) 4^logn + n^2 = Θ(n^2) 

 

▶ f(n) = O(g(n)) ↔ f ≤ g

▶ f(n) = o(g(n)) ↔ f < g

▶ f(n) = Ω(g(n)) ↔ f ≥ g

▶ f(n) = ω(g(n)) ↔ f > g

▶ f(n) = Θ(g(n)) ↔ f = g

 

단어장
generic 포괄적인, 총칭의
arithmetic 산수, 연산
quadratic 이차의
cf) linear 일차의, cubic 삼차의
precision 정확성
asymptotic 점근적
brute-force 무차별 대입
rigorous formalism 정밀한 형식주의
semantics 의미
geometric 기하학의
cf) geometric progression 등비수열, arithmetic progression 등차수열
"logb x" (pronounced as "the logarithm of x to base b", "the base-b logarithm of x", or most commonly "the log, base b, of x")
analogy 유추, 유사