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

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