In this article I will talk about how we will use to analyze and compare different types of algorithms
1.4 Why the Analysis of Algorithms?
Suppose: To get from Hanoi to Saigon, there can be many ways to do this: by plane, by bus, by train and also by bicycle.
Depending on the availability and convenience, we choose the right one for us.
Similarly, in computer science, multiple algorithms are available to solve the same problem (e.g. a sorting problem with multiple algorithms, like insertion sort, selection sort, quick sort, and many others). other algorithms).
Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.
1.5 Goal of the Analysis of Algorithms
The goal of analyzing algorithms is to compare algorithms (or solutions) mainly in terms of runtime but also in terms of other factors (e.g. memory, developer effort, etc.)
1.6 What is Running Time Analysis?
This is the process of determining how the processing time increases as the size of the problem (input size) increases.
The input size is the number of elements in the input, and depending on the problem type, the input can have many different types. The following are common input types:
- Size of an array
- Degree of a polynomial
- Number of elements in a matrix
- Number of bits in the binary representation of input
- Vertices and edges in a graph
1.7 How to Compare Algorithms
To compare an algorithm, we will use some objective measures:
- Execution times? Not a good measure because the execution time is different on each computer (hardware dependent: cpu, cables, …).
- Number of statements executed? (Number of statements executed) : Not a good metric, as the number of statements varies by programming language as well as the style of each programmer.
=> Ideal solution? : Assume that we express the running time of a given algorithm as a function of input size n (i.e. f(n)) and compare these different functions corresponding to the running times. This type of comparison does not depend on machine time, programming style, etc.