SHEN’s CLASS NOTES
Algorithm Selection Sort (A[1..n]);
1 for (i = 1, i ? n, i++) 2 3 4 5 6 End
By allowing this kind of abstraction, we can concentrate on design methodology and pay less effort to the implementation details.
If an algorithm is implemented by a program with a particular language, you may call such program an algorithm also. However, sometimes, a piece of program solves only a particular instance of a problem or several instances of a problem. For example, a program may be written to compute the average temperature from the data collected from fixed 10 locations. We can hardly call them an algorithm.
do { find j such that
}
A[j]= Min{A[i], A[i+1], …, A[n]}; A[i] ? A[j]
6
SHEN’s CLASS NOTES
1.4 Performance of an algorithm
An algorithm must be correct, highly readable, and efficient. By efficient, we mean that the algorithm must use as little memory space as possible and use as little time as possible. The memory space needed and the time used are called space complexity and time complexity, respectively. Normally, the two complexities are related to the input size. For example, sorting 10,000 numbers will take much larger space and longer time than that of sorting 100 numbers. Also, large numbers may take longer time to process than small numbers. Therefore, the space or time complexity is represented by a function that reflects the relationship between the space or time required by the algorithm and the input size. We need some assumptions on the input size.
The models of input size
There are two commonly used models.
7
SHEN’s CLASS NOTES
(1) Use the number of numbers or number of set elements
as the input size. For example, if we are given n numbers to sort, then the input size is n. In this model, we assume one memory cell will hold a number no matter how big the number is. Moreover, we assume that an operation between any two numbers takes an equal constant time. For example, (5 + 7) will takes the same amount of time as that for (10225560 + 45787899909).
(2) The number of bits (or digits) that are used for
encoding the set of input values. This model uses the number of bits fed into a computer as the input size. This model is useful when a number is so large such that the assumption that any operation takes a constant time makes no sense. Moreover, the input may contains only one number or few numbers. For example, if we want to determine if a given number x is a prime number, the input size should not be considered to be one. We need infinitely many different input sizes! For the prime number problem,
8
SHEN’s CLASS NOTES
we use lgx to be the input size because lgx bits are used to encode the number x.
In most cases, we use model (1).
How to represent the time complexity and space complexity
The time complexity of an algorithm is represented by a function from the input size to the time required by the algorithm to produce corresponding result.
The space complexity is represented by a function from the input size to the total number of different memory cells required by the algorithm to produce the result. This book will focus on the time complexity.
Because different machines have different speeds, the same algorithm may need a different time to finish on different machines. In order to fairly judge the time efficiency of an algorithm, we count the number of basic operations executed by the algorithm and use this
9
SHEN’s CLASS NOTES
number to represent the time complexity of a given algorithm. This number will not change from one machine to another. Moreover, we also ignore the effect caused by different compilers. We count the number of operations in the pseudo source code.
Because counting exactly the number of operations is difficult and not necessary, we usually pay more attention to the asymptotic behavior of the time complexity when the input size n goes to infinity. In other words, we pay more attention to the order or rate the complexity function grows when n goes to infinity.
For example, given two functions, f(n) = 2n and g(n) = 9n, we would consider them to be in the same order.
However, if f(n) = 200n and g(n) = n2, then g(n) grows much faster than f(n) although f(n) may be larger than g(n) when n is not very large. We would say that f(n) has smaller and better time complexity.
10