The Self-Taught Computer Scientist. Cory Althoff

Чтение книги онлайн.

СКАЧАТЬ 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.

Constant Time

      The most efficient order of magnitude is called constant time complexity. An algorithm runs in constant time when it requires the same number of steps regardless of the problem's size. The big O notation for constant complexity is O(1).

      Say you run an online bookstore and give a free book to your first customer each day. You store your customers in a list called customers . Your algorithm might look like this:

      free_books = customers[0]

      Your T(n) equation looks like this:

      T(n) = 1

      Your algorithm requires one step no matter how many customers you have. If you have 1,000 customers, your algorithm takes one step. If you have 10,000 customers, your algorithm takes one step, and if you have a trillion customers, your algorithm takes only one step.

When you graph constant time complexity with the number of inputs on the x-axis and the number of steps on the y-axis, the graph is flat (Figure 1.1).

      As you can see, the number of steps your algorithm takes to complete does not get larger as the problem's size increases. Therefore, it is the most efficient algorithm you can write because your algorithm's run time does not change as your data sets grow larger.

Figure 1.1 Constant complexity

Logarithmic Time

Logarithmic time is the second most efficient time complexity. An algorithm takes logarithmic time when its run time grows in proportion to the logarithm of the input size. You see this time complexity in algorithms such as a binary search that can discard many values at each iteration. If this is not clear, don't worry, because we will discuss this in depth later in the book. You express a logarithmic algorithm in big O notation as O(log n).

Figure 1.2 shows what it looks like when you plot a logarithmic algorithm.

      The required number of steps grows more slowly in a logarithmic algorithm as the data set gets larger.

Figure 1.2 Logarithmic complexity

Linear Time

The next most efficient type of algorithm is one that runs in linear time. An algorithm that runs in linear time grows at the same rate as the size of the problem. You express a linear algorithm in big O notation as O(n).

      Suppose you must modify your free book program so that instead of giving a free book to the first customer of the day, you iterate through your list of customers and give them a free book if their name starts with the letter B. This time, however, your list of customers isn't sorted alphabetically. Now you are forced to iterate through your list one by one to find the names that start with B.

      free_book = False customers = ["Lexi", "Britney", "Danny", "Bobbi", "Chris"] for customer in customers: if customer[0] == 'B': print(customer)

      When your customer list contains five items, your program takes five steps to complete. For a list of 10 customers, your program requires 10 steps; for 20 customers, 29 steps; and so on.

      This is the equation for the time complexity of this program:

      f(n) = 1 + 1 + n

      And in big O notation, you can ignore the constants and focus on the part that dominates the equation:

      O(n) СКАЧАТЬ