1
1
In this chapter
• You get a foundation for the rest of the book.
• You write your first search algorithm (binary
search).
• You learn how to talk about the running time
of an algorithm (Big O notation).
• You’re introduced
to a common technique for
designing algorithms (recursion).
introduction
to algorithms
Introduction
An
algorithm is a set of instructions for accomplishing a task. Every
piece of code could be called an algorithm,
but this book covers the
more interesting bits. I chose the algorithms in this book for inclusion
because they’re fast, or they solve interesting problems, or both. Here
are some highlights:
• Chapter 1 talks about binary search and
shows how an algorithm can
speed up your code. In one example, the number of steps needed goes
from 4 billion down to 32!
2
Chapter 1
I
Introduction to algorithms
• A GPS device uses graph algorithms (as you’ll learn in chapters 6, 7,
and 8) to calculate the shortest route to your destination.
• You can use dynamic programming (discussed in chapter 9) to write
an AI algorithm that plays checkers.
In each case, I’ll describe the algorithm and give you an example. Then
I’ll talk about the running time of the algorithm in Big O notation.
Finally, I’ll explore what other types of problems
could be solved by the
same algorithm.
What you’ll learn about performance
The good news is, an implementation of every
algorithm in this book is
probably available in your favorite language, so you don’t have to write
each algorithm yourself! But those implementations are useless if you
don’t understand the trade-offs.
In this book, you’ll learn to compare
trade-offs between different algorithms: Should you use merge sort or
quicksort? Should you use an array or a list?
Just using a different data
structure can make a big difference.
