Naive Algorithm

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

3371 ratings

University of California San Diego

Algorithmic Toolbox

3371 ratings

Course 1 of 6 in the Specialization Data Structures and Algorithms

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

From the lesson

Algorithmic Warm-up

In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!

Problem Overview3:20

Naive Algorithm5:36

Efficient Algorithm3:56

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hello everybody.

Welcome back.

Today we'll talk a little bit more about how to compute Fibonacci numbers.

And, in particular, today what we're going to do is we're going to show you how to

produce a very simple algorithm that computes these things correctly.

On the other hand, we're going to show that this algorithm is actually very slow,

and talk a little bit about how to analyze that.

So let's take a look at the definition again.

The zero'th Fibonacci number is 0.

The first Fibonacci number is 1.

And from there after each Fibonacci number is the sum of the previous two.

Now these grow pretty rapidly,

and what we would like to do is have an algorithm to compute them.

So let's take a look at how we might do this.

Well, there's a pretty easy way to go about it, given the definition.

So if n is 0, we're supposed to return 0.

And if n is 1, we're supposed to return 1.

So we could just start with a case that says if n is at most 1,

we're going to return n.

Otherwise what are we supposed to do?

Otherwise, we're supposed to return the sum of the n- 1, and

n- 2 Fibonacci numbers.

So we can just compute those two recursively, add them together, and

return them.

So, this gives us a very simple algorithm four lines long that

basically took the definition of our problem and turned it into an algorithm

that correctly computes the thing it's supposed to.

Good for us.

We have an algorithm and it works.

However, in this course, we care a lot more than just, does our algorithm work?

We also want to know if it's efficient, so we'd like to know how long this algorithm

takes to run, and there's sort of a rough approximation to this.

We're going to let T(n) denote the number of lines of code

that are executed by this algorithm on input n.

So to count this is actually not very hard.

So if n is at most one, the algorithm checks the if case,

goes to the return statement, and that's two lines of code.

Not so bad.

If n is at least two, we go to the if case.

We go to the else condition, and then run a return statement.

That's three lines of code.

However ,in this case we also need to recursively compute the n-1, and

n-2 Fibonacci numbers.

So we need to add to that however many lines of code those recursive calls take.

So all in all though, we have a nice recursive formula for T(n).

It's two as long as n is at most one.

And otherwise, it's equal to T(n) minus one plus T(n) minus two plus three.

So a nice recursive formula.

Now, if you look at this formula for a little bit, you'll notice that it looks

very similar to the original formula that we used to define the Fibonacci numbers.

Each guy was more or less the sum of the previous two.

And in fact, from this you can show pretty easily

that T( n) is at least the n'th Fibonacci number for all n.

And this should be ringing some warning bells because we know that the Fibonacci

numbers get very, very, very large, so T(n) must as well.

In fact, T(100) is already 1.77 times 10 to the 21.

1.77 sextillion.

This is a huge number.

Now, suppose we were running this program on a computer that

executed a billion lines of code a second.

It ran it at a gigahertz.

It would still take us about 56,000 years to complete this computation.

Now, I don't have 56,000 years to wait for my computer to finish.

You probably don't either, so this really is somehow not acceptable,

if we want to compute Fibonacci numbers of any reasonable size.

So what we'd really like is we'd like a better algorithm.

And we'll get to that next lecture.

But first we should talk a little bit about why this algorithm is so slow.

And to see that, maybe the clearest way to demonstrate it is to look at

all of the recursive calls this algorithm needs in order to compute its answer.

So, if we want to compute the n'th Fibonacci number,

we need to make recursive calls to compute the n-1,and n-2 Fibonacci numbers.

To compute the n-1, we need the n-2 to the n-3.

To compute the n-2, we need the n-3, and n-4, and it just keeps going on and on.

From there we get this big tree of recursive calls.

Now if you'll look at this tree a little bit closer,

it looks like we're doing something a little bit silly.

We're computing Fn-3, three separate times in this tree.

And the way with our algorithm works, every time we're asked to compute it,

since this is a new recursive call, we compute the whole thing from scratch.

We recompute Fn-4, and Fn-5, and then, add them together and get our answer.

And it's this computing the same thing over and

over again that's really slowing us down.

And to make it even more extreme, let's blow up the tree a little bit more.

Fn-4 actually gets computed these five separate times by the algorithm.

And as you keep going down more and more and more times,

are you just computing the same thing over and over again?

And this is really the problem with this particular algorithm, but

it's not clear immediately that we can do better.

So, come back next lecture and we'll talk about how to get around this difficulty,

and actually get a fairly efficient algorithm.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play