Java Reference
In-Depth Information
If you execute this code with
n
equal to ten thousand (10000), you will get the right answer of 50005000
for each of the algorithms. Now change the value of
n
to one hundred thousand (100000), and execute
the code again. Once more, you will get the correct answer, which this time is 5000050000. However,
you should notice a delay in seeing the result for Algorithm B. Now try one million (1000000) for the
value of
n
. Again you will get the correct answer—500000500000—but you will have to wait even lon-
ger for the result from Algorithm B. The wait might be long enough for you to suspect that something is
broken. If not, try a larger value of
n
.
The previous simple code for Algorithm B takes a noticeably long time to execute, much
longer than either of the other two algorithms. If it were the only algorithm you tried, what
should you do? Use a faster computer? While that might be a solution, it's clear that we should
use a different algorithm.
Note:
As the previous example shows, even a simple program can be noticeably inefficient.
Note:
If an algorithm takes longer to execute than is practical, try to reformulate it to make
it more efficient of time.
4.3
The previous section should have convinced you that a program's efficiency matters. How can we
measure efficiency so that we can compare various approaches to solving a problem? In the previ-
ous section, we computed the sum of the first
n
consecutive integers in three different ways. We
then observed that one was noticeably slower than the others as the value of
n
increased. In general,
however, implementing several ideas before you choose one requires too much work to be practi-
cal. Besides, a program's execution time depends in part on the particular computer and the pro-
gramming language used. It would be much better to measure an
algorithm's
efficiency before you
implement it.
For example, suppose that you want to go to a store downtown. Your options are to walk, drive
your car, ask a friend to take you, or take a bus. What is the best way? First, what is your concept of
best? Is it the way that saves money, your time, your friend's time, or the environment? Let's say that
the best option for you is the fastest one. After defining your criterion, how do you evaluate your
options? You certainly do not want to try all four options so you can discover which is fastest. That
would be like writing four different programs that perform the same task so you can measure which
one is fastest. Instead you would investigate the “cost” of each option, considering the distance, the
speed at which you can travel, the amount of other traffic, the number of stops at traffic lights, the
weather, and so on. That is, you would consider the factors that have the most impact on the cost.
VideoNote
Measuring efficiency
4.4
The same considerations apply when deciding what algorithm is best. Again, we need to define what we
mean by best. An algorithm has both time and space requirements, called its
complexity
,
that we can
measure. When we assess an algorithm's complexity, we are not measuring how involved or difficult it
is. Instead, we measure an algorithm's
time complexity
—the time it takes to execute—or its
space
complexity
—the memory it needs to execute. Typically we analyze these requirements separately. So a
“best” algorithm might be the fastest one or the one that uses the least memory.
