Сложность алгоритмов

Начнем с того, что такое алгоритм?

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

Давайте изобразим работу алгоритма наглядно.

a = [3,5,8,1,9,7]
n = 6
for i in a:
    print(i)

Обозначим время выполнения программы T, а N – за длину списка. Счетчик i последовательно будет равняться по порядку каждому значению из списка a и печатать их на экран, поэтому, нетрудно догадаться, что время выполнения программы будет прямо пропорционально количеству элементов (T~N). 

Но что же будет, если внутрь этого цикла поместить еще один?

a = [3,5,8,1,9,7]
n = 6
for i in a:
    for j in a:
        print(i,j)

Тут ситуация уже становится интереснее, потому что для каждого значения i мы заново просматриваем весь массив и подставляем ему в пару все числа j. Получается, что вложенный цикл выполнится N раз, проверяя при этом N чисел (объем нашего списка), а это уже  операций.

Значит, время выполнения будет пропорционально уже квадрату количества элементов. Интуитивно понятно, что каждый последующий вложенный цикл даёт нам уменьшение эффективности еще в N раз. Таким образом, нужно стараться избегать вложенных циклов. Однако, это не всегда возможно: сортировка методом пузырька, да и большинство других, обязывают нас использовать цикл в цикле.

В кодификаторе можно встретить запись, что эффективным считается алгоритм быстрее O(), но что она означает не понятно. Давайте разбираться. В информатике и программировании нотация «О-большое» используется в качестве меры сложности алгоритма. Фактически надпись О(N) говорит нам, что время работы алгоритма растет не быстрее, чем некоторая константа, умноженная на N. Эта оценка, в основном, достаточно точна при большом N.

• O(1) – постоянная сложность. Думаю, из названия понятно, что время выполнения алгоритма постоянно. Например, если мы пробегаемся циклом по массиву постоянной длины, которая не зависит от введенных данных.

• O(log N) – логарифмическая сложность. Например, нахождение элемента в отсортированном массиве с помощью двоичного поиска.

Метод работает по стратегии «Разделяй и Властвуй», при котором весь массив делится пополам, определяется в какой части находится данное число, и эта часть снова делится надвое. Деление происходит до тех пор, пока не обнаружится наличие искомого элемента или его отсутствие.

• O(N) – линейная сложность. Например, алгоритм поиска минимального или максимального элемента в неотсортированном массиве. Узнать, какой из них больший/меньший можно, сравнив  его со всеми остальными, а для этого необходимо пройтись по всем N элементам массива.
• O(N log N) – квазилинейная сложность. Например, при сортировке слиянием.

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

• O(N2) – квадратичная сложность. Такую сложность имеет, например, популярный алгоритм пузырьковой сортировки, когда сравниваются два соседних элемента и меняются местами в зависимости от того, который из них больше.

• O(СN) – экспоненциальная сложность. Нахождение решения задачи коммивояжёра с помощью динамического программирования, но это уже далеко не тема ЕГЭ.

Помимо избегания вложенных циклов, нужно экономить и память. Объявляя переменные, мы резервируем ячейки памяти. Например, в PascalABC переменная типа Integer весит 2 байта, а переменная типа Double – целых 10 байт.

Поэтому память можно экономить, соблюдая следующие советы:

• Верно присваивать тип самой переменной. 
• Не сохранять вводимые данные в массив/список или переменные, а анализировать сразу при вводе (это мы научимся делать в следующих статьях).
• Экономно использовать сами переменные, по возможности использовать одну для разных целей (это очень слабый метод оптимизации и экономии, поэтому им можно пренебречь).

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