Data Structures (Into Java)

Data Structures (Into Java)



https://FreeCourseWeb.com

English | PDF | 2013 | 251 Pages | ISBN : N/A | 1.47 MB

The obvious way to answer to the question “How fast does such-and-such a program run?” is to use something like the UNIX time command to find out directly. There are various possible objections to this easy answer. The time required by a program is a function of the input, so presumably we have to time several instances of the command and extrapolate the result. Some programs, however, behave fine for most inputs, but sometimes take a very long time; how do we report (indeed, how can we be sure to notice) such anomalies? What do we do about all the inputs for which we have no measurements? How do we validly apply results gathered on one machine to another machine?
The trouble with measuring raw time is that the information is precise, but limited: the time for this input on this configuration of this machine. On a different machine whose instructions take different absolute or relative times, the numbers don’t necessarily apply. Indeed, suppose we compare two different programs for doing the same thing on the same inputs and the same machine. Program A may turn out faster than program B. This does not imply, however, that program A will be faster than B when they are run on some other input, or on the same input, but some other machine.