第3章データ構造とアルゴリズム

In the 1970s, computer scientists applied asymptotic notation, a mathematical notation that formally defines the order of growth. We can use Big O notation to describe the time complexity of the sequential search algorithm. In general, we say a function f(N) is in the class of O(g(N)), denoted by f(N) = O(g(N)) or f(N) in O(g(N)), if when N tends to infinity, the ratio f(N)/g(N) is upper bounded by some constant. The function g(N) is usually some simple function that defines the order of growth such as g(N) = 1 (constant function), g(N) = N (linear function), g(N) = log N (logarithmic function), or other functions as follows:

• In the best case, the order of growth of sequential search is in O(1).

• In the worst case, the order of growth of sequential search is in O(N) with respect to N, the number of words in the list.

The constant order of growth is described in Big O notation as “O(1)” while the linear order of growth is described in Big O notation as “O(N) with respect to N, the size of the problem.” Big O notation formalizes the concept of a prediction. Given the size of the problem, N, calculate how long it takes to run the algorithm on a problem of that size. For large lists, in order to double the worst-case runtime of sequential search, we would need to double the size of the list.

O(1) and O(N) are not the only orders of growth.

• O(1), or constant.

• O(log N), or logarithmic.

• O(N), or linear.

• O(N log N), or linearithmic.

• O(N²), or quadratic.

• O(N³), or cubic.

• O(2^N), O(3^N), . . . , or exponential.

• O(N!), or factorial.

The O(log N), or logarithmic, order of growth appears quite often in algorithm analysis. The logarithm of a large number tells how many times it needs to be divided by a small number until it reaches 1. The binary logarithm, or log2, tells how many times a large number needs to be divided by 2 until it reaches 1. In the worst case, the time complexity of sequential search is in O(N) with respect to N, the number of words in the list, since each repetition of sequential search rules out one remaining element. How about binary search? In the worst case, the time complexity of binary search is in O(log N) with respect to N, the number of words in the list, since each repetition of binary search rules out half the remaining elements.

Another way to understand orders of growth is to consider how a change in the size of the problem results in a change to the resource usage. When we double the size of the input problem, algorithms in each order of growth respond differently (Figure 3.15).

• O(1) algorithms will not require any more resources.

• O(log N) algorithms will require 1 additional resource unit.

• O(N) algorithms will require 2 times the number of resources.

• O(N log N) algorithms will require a little more than 2 times the number of resources.

• O(N²) algorithms will require 4 times the number of resources.

• O(N³) algorithms will require 8 times the number of resources.

• O(2^N), O(3^N), . . . algorithms will require the squared or cubed number of resources.

• O(N!) algorithms will require even more.

This growth compounds, so quadrupling the size of the problem for an O(N²) algorithm will require 16 times the number of resources. Algorithm design and discovery is often motivated by these massive differences between orders of growth. Note that this explanation of how each order of growth responds differently oversimplifies the problem. Rigorously speaking, a function f(N) expressed in the big-O notation as being is in the class of O(g(N)) can be much more complex than the simple function g(N). For example, f(N) = 4log N + 100 log(log N) is in O(log N), but when N doubles, f(2N) is definitely not just one unit more than the original function f(N). A similar argument applies for all other functions other than the constant O(1) function.

As the size of the problem increases, algorithmic complexity becomes a larger and larger factor. For problems dealing with just 1,000 elements, the time it would take to run an exponential-time algorithm on that problem exceeds the current age of the universe. In practice, across applications working with large amounts of data, O(N log N) is often considered the limit for real-world algorithms. Even then, O(N log N) algorithms cannot be run too frequently. For algorithms that need to run frequently on large amounts of data, algorithm designers target O(N), O(log N), or O(1).