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

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) = n

In a linear algorithm, as n gets bigger, the number of steps your algorithm takes increases by however much n increases (Figure 1.3).

Figure 1.3 Linear complexity