Сложность алгоритма. Big O notation

Cheat sheet Big O notation:

Часто во время оптимизации с целью сэкономить несколько циклов ЦП (центрального процессора) будет возникать ситуация, в которой код так или иначе будет работать медленно.

Представь, что ты только что закончил писать код для решения конкретной проблемы. Ввод представляет собой массив значений, и твой код вычисляет некоторый результат из этого массива. Ты тестируешь код и обнаруживаешь, что он достаточно быстр для тестовых данных.

Позже ты получишь набор реально больших данных из производственных систем. В сто раз больше, чем тестовые данные. «Хорошо, — говоришь ты себе, — если я запущу тест с этими входными данными, мой код займет в сто раз больше времени, чем тестовые данные».

К твоему удивлению код занимает в тысячу раз больше времени! Что случилось?

Проблема размера входящих данных

Всякий раз, когда ты разрабатываешь функцию, которая работает с набором входных данных, спрашивай себя:

«Как мой алгоритм масштабируется с размером входных данных?»

Другими словами, как изменится время выполнения, если размер входных данных удвоится, утроится, учетверится и т. д.?

Чтобы ответить на этот вопрос, нужно посмотреть, как твой код обрабатывает входные данные.

От размера ввода до времени выполнения

Input может означать что угодно: файл для обработки, одно число в массиве, символ в строке, строку в списке строк, запись в наборе результатов запроса к базе данных и так далее. Точный тип ввода здесь не имеет значения. Учитывается количество вводимых элементов.

Но пока давай предположим, что у нас есть массив целых чисел для обработки и некоторый воображаемый код, который делает пару вещей с этим массивом:

Сначала цикл проходит по массиву и умножает каждое число на два. Для n элементов циклу нужно затратить n единиц времени.

Затем по коду выполняются два вложенных цикла. Внешний не делает ничего, кроме выполнения внутреннего, поэтому мы можем пренебречь временем, которое использует этот цикл. Внутренний цикл выполняется n*n несколько раз, и ему требуется в четыре раза больше времени, чем одиночному циклу для обработки каждого элемента. Таким образом, для наших n входных элементов двойной цикл выполняется для 4*n*n единиц времени.

Далее в коде мы вставляем каждый элемент в сбалансированное двоичное дерево поиска. Каждая вставка занимает примерно log(n+1) единиц времени (высота дерева элементов равна log(n+1)), поэтому вставка n элементов будет занимать n*log(n+1) единицы времени (log здесь означает логарифм по основанию 2).

Таким образом, у нас есть время выполнения 4*n^2 + n + n*log(n) единицы времени.

Получилась громоздкая формула, не так ли?

Нам не нужна вся часть сложности алгоритма, мы возьмем ее наиболее весомую часть.