Читать книгу The Self-Taught Computer Scientist - Cory Althoff - Страница 19

There is often more than one algorithm we can use to solve a problem. For example, there are several different ways to sort a list. When several algorithms solve a problem, how do you know which one is best? Is it the simplest? The fastest? The smallest? Or something else?

One way to judge an algorithm is by its run time. An algorithm's run time is the amount of time it takes your computer to execute an algorithm written in a programming language like Python. For example, here is an algorithm in Python that counts from 1 to 5 and prints each number:

for i in range(1, 6): print(i)

You can measure this algorithm's run time using Python's built-in time module to track how long your computer takes to execute it:

import time start = time.time() for i in range(1, 6): print(i) end = time.time() print(end – start) >> 1 >> 2 >> 3 >> 4 >> 5 >> 0.15141820907592773

When you run your program, it prints the numbers from 1 to 5 and outputs the time it took to execute. In this case, it took 0.15 seconds.

Now, rerun your program:

import time start = time.time() for i in range(1, 6): print(i) end = time.time() print(end – start) >> 1 >> 2 >> 3 >> 4 >> 5 >> 0.14856505393981934

The second time you run your program, you should see a different run time. If you rerun your program, you will see yet another run time. The algorithm's run time keeps changing because the available processing power your computer has when it runs your program varies and in turn affects the program's run time.

Further, this algorithm's run time would be different on another computer. If you run it on a computer with less processing power, it would be slower, whereas it would be faster on a more powerful computer. Furthermore, this program's run time is affected by the programming language you wrote it in. For example, the run time would be faster if you run this same program in C because C can be faster than Python.

Because an algorithm's run time is affected by so many different variables, such as your computer's processing power and the programming language, run time is not an effective way to compare two algorithms. Instead, computer scientists compare algorithms by looking at the number of steps they require. You can input the number of steps involved in an algorithm into a formula that can compare two or more algorithms without considering the programming language or computer. Let's take a look at an example. Here is your program from earlier that counts from 1 to 5:

for i in range(1, 6): print(i)

Your program takes five steps to complete (it goes through a loop five times and prints i each time). You can express the number of steps your algorithm requires with this equation:

f(n) = 5

If you make your program more complicated, your equation will change. For example, you may want to keep track of the sum of all the numbers you are printing:

count = 0 for i in range(1, 6): print(i) count += i

Now, your algorithm takes 11 steps to complete. First, it assigns the variable count to zero. Then, it prints five numbers and increments five times (1 + 5 + 5 = 11).

This is the new equation for your algorithm:

f(n) = 11

What happens if you change the 6 in your code to a variable?

count = 0 for i in range(1, n): print(i) count += i

Your equation changes to this:

f(n) = 1 + 2n

Now the number of steps your algorithm takes depends on whatever the value of n is. The 1 in the equation represents the first step: count = 0 . Then, there are two times n steps after that. For example, if n is 5, f(n) = 1 + 2 × 5. Computer scientists call the variable n in an equation that describes the number of steps in an algorithm the size of the problem. In this case, you could say the time it takes to solve a problem of size n is 1 + 2n, or in mathematical notation, T(n) = 1 + 2n.

An equation describing the number of steps in an algorithm is not very helpful, however, because, among other things, you can't always reliably count the number of steps in an algorithm. For example, if an algorithm has many conditional statements, you have no way of knowing which of them will execute in advance. The good news is, as a computer scientist, you don't care about the exact number of steps in an algorithm. What you want to know is how an algorithm performs as n gets bigger. Most algorithms perform fine on a small data set but may be a disaster with larger data sets. Even the most inefficient algorithm will perform well if n is 1. In the real world, however, n will probably not be 1. It may be several hundred thousand, a million, or more.

The important thing to know about an algorithm is not the exact number of steps it will take but rather an approximation of the number of steps it will take as n gets bigger. As n gets larger, one part of the equation will overshadow the rest of the equation to the point that everything else becomes irrelevant. Take a look at this Python code:

def print_it(n): # loop 1 for i in range(n): print(i) # loop 2 for i in range(n): print(i) for j in range(n): print(j) for h in range(n): print(h)

What part of this program is most important for determining how many steps your algorithm takes to complete? You may think both parts of the function (the first loop and the second loop containing other loops) are important. After all, if n is 10,000, your computer will print many numbers in both loops.

It turns out that the following code is irrelevant when you are talking about your algorithm's efficiency:

# loop 1 for i in range(n): print(i)

To understand why, you need to look at what happens as n gets bigger.

Here is the equation for the number of steps in your algorithm:

T(n) = n + n**3

When you have two nested for loops that take n steps, it translates to n**2 (n to the second power) because if n is 10, you have to do 10 steps twice, or 10**2. Three nested for loops are always n**3 for the same reason. In this equation, when n is 10, the first loop in your program takes 10 steps, and the second loop takes 10³ steps, which is 1,000. When n is 1,000, the first loop takes 1,000 steps, and the second loop takes 1,000³, which is 1 billion.

See what happened? As n gets bigger, the second part of your algorithm grows so much more quickly that the first part becomes irrelevant. For example, if you needed this program to work for 100,000,000 database records, you wouldn't care about how many steps the first part of the equation takes because the second part will take exponentially more steps. With 100,000,000 records, the second part of the algorithm would take more than a septillion steps, which is 1 followed by 24 zeros, so it is not a reasonable algorithm to use. The first 100,000,000 steps aren't relevant to your decision.

Because the important part of an algorithm is the part that grows the fastest as n gets bigger, computer scientists use big O notation to express an algorithm's efficiency instead of a T(n) equation. Big O notation is a mathematical notation that describes how an algorithm's time or space requirements (you will learn about space requirements later) increase as the size of n increases.

Computer scientists use big O notation to create an order-of-magnitude function from T(n). An order of magnitude is a class in a classification system where each class is many times greater or smaller than the one before. In an order-of-magnitude function, you use the part of T(n) that dominates the equation and ignore everything else. The part of T(n) that dominates the equation is an algorithm's order of magnitude. These are the most commonly used classifications for order of magnitude in big O notation, sorted from the best (most efficient) to worst (least efficient):

 Constant time

 Logarithmic time

 Linear time

 Log-linear time

 Quadratic time

 Cubic time

 Exponential time

Each order of magnitude describes an algorithm's time complexity. Time complexity is the maximum number of steps an algorithm takes to complete as n gets larger.

Let's take a look at each order of magnitude.