Not all programs are created equal. In this course, we'll focus on writing quality code that runs correctly and efficiently. We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

Loading...

来自 University of Toronto 的课程

学习编程：撰写高质量代码

304 个评分

Not all programs are created equal. In this course, we'll focus on writing quality code that runs correctly and efficiently. We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

从本节课中

Week 3

- Jennifer CampbellAssociate Professor, Teaching Stream

Department of Computer Science - Paul GriesAssociate Professor, Teaching Stream

Department of Computer Science

Up to now, our primary focus has been on writing correct code.

Next, we'll analyze our algorithms to determine the amount of time that they

take to run, relative to the size of the input.

In up coming lectures, it'll apply what you learned in this one, to analyze

algorithms and compare them in order to determine which one to use.

To analyze our algorithms, we're not going to measure them by timing them.

Instead, we're going to read the code and look at the number of steps that they'll

take for a particular input size. For example, in this lecture, we're going

to write several functions that print integers, and we're going to focus on how

many times the print function is called in each of our functions.

The first function that we'll analyze is print ints.

This function prints the integers from 1 up to n inclusive.

Let's call this function. We'll run the module and call print_ints

with an argument of ten. In this case, the print function is

called ten times. That is, the for loop iterates ten times.

What if this function were called with the argument 20?

In that case, the for loop would iterate 20 times, and he print function would be

called 20 times. And what about 40?

There would be 40 iterations of the loop. Let's plot this so that we have a visual

representation of the run time. On one axis, we'll have n, the input to

the function. And on the other axis, we'll have the

number of steps that the function will execute for a given n.

For this problem, the steps that we're measuring are the print function calls.

Notice that the number of steps is proportional to the size of n.

Next, let's consider another function. Print odd ints, prints the odd integers

from one to n inclusive. We'll call this function for the argument

10 as well. Print was only count five times.

If the argument were 20, it would be called ten times.

And if the argument were 40, it would be called 20 times.

For the first function, the number of print function calls was equal to n.

For this one, it's roughly half of n depending on whether n is odd or even.

[UNKNOWN] this as well. We can see that the number of steps still

proportional to the size of n, it's roughly half of n.

This function and the first are both considered linear functions.

The run time grows linearly with respect to the size of the input n.

Next up, we'll analyze function print pairs.

It prints all combinations of pairs of integers from 1 to n, inclusive.

We're going to start by calling this function a couple of times.

First, we'll call print pairs with an argument 2.

In that case, four pairs are printed. We'll call it again with the argument 3.

In this case, we've got 9 pairs being printed.

Now, with the argument 4, there are 16 pairs printed.

Do you see a pattern? For the argument n, the print function is

called n squared times. When analyzing algorithms, we don't

always have the luxury of running code. Sometimes, we do analysis before writing

code. To determine whether it's even worth

writing, we'll analyze this function by reading the code, and the same could be

done with pseudo code. The print function call is inside the

inner loop of a nested loop. When the inner loop is executed, it will

iterate n times. And the inner loop is executed once for

each iteration of the outer loop. The outer loop will execute n times as

well. So with n iterations of the outer loop

times n iterations of the inner loop, print is called n squared times.

This time, the number of steps is proportional to the size of the input

squared. We'll plot this as well.

As n grows, the number of steps is growing more quickly than it did for the

other 2 algorithms. If we had 2 algorithms that solved the

same problem and one had linear run time while the other had quadratic run time,

we'd want to use the one with linear run time if we were trying to pick the most

efficient algorithm. Let's consider one more function.

This function, print double step, also prints the integers from 1 to n

inclusive. But rather than using a step size of one

or two, like the previous functions, this step size varies.

The step size is the difference between a pair of numbers in the sequence.

The initial step size would be 1. The next step would be 2, then 4, 8, 16,

32 and so on. Let's consider how many integers are

printed for various values of n. Let's start with n equal to 4.

In that case, three integers would be printed.

The integers 1, 2 and 4. How about when n refers to 5?

In that case, there would still only be three integers printed, the ints 1, 2,

and 4. The same goes for when n refers to 6 and

7. It's not until n refers to 8 that that we

then have a fourth integer printed. When n refers to the values 8 through 15,

there are still only four ints printed. It's only when n refers to 16 that there

would be a fifth int printed. And then, when n refers to 32, twice

that, six would be printed. When it's twice that, 64, seven would be

printed. Every time n is doubled, an additional

integer is printed. For the previous function, we said the

number of steps is equal to n squared. For this function, the number of steps is

proportional to log base 2 of m. This algorithm is logarithmic.

As the side of n grows, the number of steps grows more slowly than it did for

the linear and quadratic algorithms.