Algorithm

Algorithm : Step by step procedure

Problem : Question to seek answer
Parameter : Variables which are not assigned specific values
Instance : Parameter which are assigned specific value
Solution : Answer to the problem

Pseudocode : A language for algorithm, more free than Programming language
Keytype : Key가 되는 핵심 값들의 Datatype

Sequential Search 
- 순차탐색, 앞에서부터 차례대로 찾아본다.   Θ(n)

Exchange sort 
- Pivot이 맨 앞부터 진행하면서 그 자리 번째로 작은 숫자를 찾아서 Exchange한다. Θ(n^2)
ex) 32145 -> 23145 -> 13245 -> 12345

Binary Search
- 이진탐색, UP-DOWN 방식으로 가운데를 기준으로 1/2 씩 나누면서 Search Θ(logn)
※Sorting은 이미 되어있다는 가정하에 Search진행

Fibonacci Sequence
- 0 1 1 2 3 5 8 ........
- f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2) {n>=2}
- Recursive Version : Θ(2^(n/2)), 같은 연산을 중복해서 여러번 진행하여 비 효율적이다.
- Iterative Version : T(n) = n+1 , Θ(n)

Time Complexity Analysis

=> Determination of how many times the basic operation is done for each value of input size
1) Every-case analysis
2) Worst-case analysis
3) Average-case analysis
4) Best-case analysis

Every-case analysis 
T(n) : Every-case time complexity
=> The number of times the algorithm does the basic operation for an instance of size n

Worst-case analysis
W(n) : Worst-case time complexity
=>The maximum number of times the algorithm will ever do its operation for an input size of n
=> If T(n) is exists, then clearly W(n) = T(n)

Average-case analysis
A(n) : Average-case time complexity
=> The average(Expected value) of the number of times the algorithm does the basic operation for an input size of n
=> If T(n) is exists, then A(n) = T(n)

Best-case analysis
B(n) : Best-case time complexity
=> The minimum number of times the algorithm will ever do its basic operation for an input size of n
=> If T(n) is exists, then B(n) = T(n)