Начнем с того, что алгоритм – это точная инструкция, однозначно определяющая вычислительный процесс. Разумеется, очень хорошо иметь возможность оценить ресурсы, затрачиваемые на выполнение этого алгоритма. Результатом данной оценки и является сложность, которая показывает, какое количество памяти и времени требуется для алгоритма.
Давайте изобразим работу алгоритма наглядно:
Проанализируем простенькую программку:
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 чисел (объем нашего списка), а это уже N2 операций.
Значит, время выполнения будет пропорционально уже квадрату количества элементов. Интуитивно понятно, что каждый последующий вложенный цикл даёт нам уменьшение эффективности еще в N раз. Таким образом, нужно стараться избегать вложенных циклов. Однако, это не всегда возможно: сортировка методом пузырька, да и большинство других, обязывают нас использовать цикл в цикле.
Эффективность по времени
В кодификаторе можно встретить запись, что эффективным считается алгоритм быстрее O(N2), но что она означает не понятно. Давайте разбираться. В информатике и программировании нотация «О большое» используется в качестве меры сложности алгоритма. Фактически надпись О(N) говорит нам, что время работы алгоритма растет не быстрее, чем некоторая константа, умноженная на N. Эта оценка, в основном, достаточно точна при большом N.
Примеры основных сложностей
O(1) – постоянная сложность. Думаю, из названия понятно, что время выполнения алгоритма постоянно. Например, если мы пробегаемся циклом по массиву постоянной длины, которая не зависит от введенных данных.
O(log N) – логарифмическая сложность.Например, нахождение элемента в отсортированном массиве с помощью двоичного поиска.
Двоичный(бинарный) поиск – метод поиска определенного значения в отсортированном списке. Метод работает по стратегии «Разделяй и Властвуй», при котором весь массив делится пополам, определяется в какой части находится данное число, и эта часть снова делится надвое. Деление происходит до тех пор, пока не обнаружится наличие искомого элемента или его отсутствие.
O(N) – линейная сложность. Например, алгоритм поиска минимального или максимального элемента в неотсортированном массиве. Узнать, какой из них больший/меньший можно, сравнив его со всеми остальными, а для этого необходимо пройтись по всем N элементам массива.
O(N log N) – квазилинейная сложность. Например, при сортировке слиянием.
Сортировка слиянием – метод сортировки, при котором исходный массив разбивается пополам, до тех пор, пока размер получаемого массива не станет равным единице. Далее выполняется слияние: два единичных массива сливаются в общий, при этом из каждого выбирается меньший элемент и записывается слева направо в результирующий массив. После чего из двух результирующих массивов собирается третий, и так далее. Потом элементы результирующего массива переносятся в основной.
O(N2) – квадратичная сложность. Такую сложность имеет, например, популярный алгоритм пузырьковой сортировки, когда сравниваются два соседних элемента и меняются местами в зависимости от того, который из них больше.
O(СN) – экспоненциальная сложность. Нахождение решения задачи коммивояжёра с помощью динамического программирования, но это уже далеко не тема ЕГЭ.
Эффективность по памяти
Помимо избегания вложенных циклов, нужно экономить и память. Объявляя переменные, мы резервируем ячейки памяти. Например, в PascalABC переменная типа Integer весит 2 байта, а переменная типа Double – целых 10 байт.
Поэтому память можно экономить, соблюдая следующие советы:
- Верно присваивать тип самой переменной.
- Не сохранять вводимые данные в массив/список или переменные, а анализировать сразу при вводе (это мы научимся делать в следующих статьях).
- Экономно использовать сами переменные, по возможности использовать одну для разных целей (это очень слабый метод оптимизации и экономии, поэтому им можно пренебречь).
Таким образом, мы получаем вполне адекватное в рамках ЕГЭ определение эффективной программы: сложность должна быть ниже квадратичной, а используемая память не должна зависеть от количества вводимых чисел.
А вот как этого добиться мы с вами разберемся уже в следующих статьях)