Useful algorithms and data structures

Algorithmic improvements are especially effective in increasing performance because they typically allow the application to scale better with increasingly large inputs.

Algorithm running times can be classified according to their computational complexity, a characterization of the resources required to perform a task. Such classification is expressed through the Big-O notation, an upper bound on the operations required to execute the task, which usually depends on the input size.

For example, incrementing each element of a list can be implemented using a for loop, as follows:

    input = list(range(10))
    for i, _ in enumerate(input):
        input[i] += 1 

If the operation does not depend on the size of the input (for example, accessing the first element of a list), the algorithm is said to take constant, orO(1), time. This means that, no matter how much data we have, the time to run the algorithm will always be the same.

In this simple algorithm, the...