1. ALGORITHM?
An algorithm is a sequence of unambiguous instructions for solving a problem for obtaining a required output for any legitimate input in a finite amount of time.
2. IMPORTANT FACTOR OF ALGORITHMS
- Correctness
- Time efficiency
- Space efficiency
2-1. Time Complexity the basic techniques for calculate time efficiency
Time complexity is the amount of computer time a program needs to run.
To measure,
1. Count a particular operation (operation counts)
2. Count the number of steps (step counts)
3. Asymptotic complexity
To measure,
1. Count a particular operation (operation counts)
2. Count the number of steps (step counts)
3. Asymptotic complexity
- Worst-case ; an upper bound on the running time for any input of given size
- Average-case ; Assume all inputs of a given size are equally likely,
- Best-case ; The lower bound on the running time
Algorithm complexity is rough estimation of the number of steps performed by given computation depending on the size of the input data.
- O-notation (Big O notation) : provides an upper bound for the function f
- Omega(Ω) notation : provides a lower-bound
- Theta(Q) notation : used when an algorithm can be bounded both from above and below by the same function.
* Typical Complexities