As an example, consider a sorting task. Suppose you need to sort a million numbers (social security numbers,
for example). You have the choice of using your current computer with a merge sort program, or of buying
a new computer, which is 10 times faster, but which uses an insertion sort.
The insertion sort on the new computer will require on the order of (106)2, or a million million cycles, while
the merge sort will require on the order of 106(lg 106), or 106(20), or 20 million cycles. Even when it runs on
your old computer, the merge sort will still run four orders of magnitude faster than the insertion sort on the
new machine. If it takes 20 seconds to run the merge sort on your old machine, it will take over 27 hours to run
the insertion sort on the new machine!
Algorithm design should be considered important technology. A better algorithm can make the difference
between being able to solve the problem or not, and a better algorithm can make a much greater difference than
any near-term improvement in hardware speed.
FORMAL MODELS OF COMPUTATION
The theory of computing has advanced by adopting formal models of computation whose properties can be
explored mathematically. The most influential model was proposed by the mathematician Alan Turing in 1936.
Pages:
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75