"Информатика", Поляков К.Ю., Еремин Е.А.
Сложность алгоритма показывает, как меняется количество вычислительных действий при увеличении объёма входных данных. Эта оценка помогает понять, справится ли алгоритм с длинным списком или большой задачей, и выбрать более подходящий способ решения. Для начала важно определить размер данных n и посчитать повторения команд: один проход обычно даёт линейный рост, а вложенный перебор — квадратичный.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сложность алгоритма — оценка того, сколько вычислительных действий потребуется для решения задачи в зависимости от размера входных данных. Иначе говоря, это способ описать, как меняется объём работы, если данных становится больше. Такая оценка нужна, чтобы сравнивать алгоритмы и заранее замечать, какой из них может оказаться слишком медленным для большой задачи.
Размер входных данных — количество элементов или других исходных данных, от которого зависит объём работы алгоритма. Его часто обозначают буквой n: например, для списка из 20 чисел n = 20. Выбор n помогает выразить число повторений и действий общей формулой, а не считать работу только для одного конкретного списка.
Линейная сложность — зависимость числа действий примерно как n. Если размер данных увеличить в несколько раз, число действий обычно увеличится примерно во столько же раз. Такой рост часто возникает, когда алгоритм один раз проходит по всем элементам и выполняет на каждом шаге постоянное число команд.
Квадратичная сложность — зависимость числа действий примерно как n². При увеличении n в несколько раз число действий растёт примерно в квадрат этого множителя. Этот вид роста часто появляется, когда для каждого элемента выполняется ещё один проход по всему списку; распознавание такой структуры помогает оценить её последствия для больших данных.
Чтобы оценить сложность, сначала выбирают размер входных данных n и считают повторяемые действия алгоритма. Например, для списка удобно принять за n число его элементов, а затем выяснить, сколько раз алгоритм обращается к ним. Такой порядок нужен потому, что без выбранного размера нельзя связать объём задачи с количеством работы и сравнить разные случаи.
Если цикл проходит по всем n элементам, важно посмотреть, что происходит внутри его тела. Когда на каждом шаге выполняется постоянное число команд, общее число действий примерно равно этому числу, умноженному на n. Например, если элемент проверяется один раз и результат обновляется за постоянное число действий, удвоение списка примерно удваивает объём работы — поэтому рост линейный.
Иная картина возникает, когда для каждого элемента запускается ещё один проход по всем элементам. Внешний цикл даёт примерно n шагов, и на каждом из них внутренний цикл делает ещё примерно n шагов. Поэтому суммарно получается около n × n, то есть n² действий; это называют квадратичным ростом. Вложенность важна именно потому, что внутренние повторения выполняются заново для каждого шага внешнего цикла.
Сложность не равна времени в секундах на конкретном компьютере. Один и тот же алгоритм может работать быстрее на мощном устройстве, а разные языки и реализации могут выполнять одинаковые действия с разной скоростью. Оценка сложности отвлекается от этих деталей и показывает общий характер роста затрат, когда n увеличивается.
При сравнении алгоритмов одной задачи нужно смотреть, насколько быстро растёт число действий, особенно для больших входных данных. На малом списке разница между несколькими сотнями и тысячей действий может быть почти незаметна, но при увеличении n квадратичный рост быстро обгоняет линейный. Поэтому оценка позволяет рассуждать о пригодности алгоритма ещё до запуска на огромном наборе данных.
График сопоставляет значения n и примерное число действий для двух видов роста. При n = 5 значения n и n² равны 5 и 25, а при n = 10 — 10 и 100; квадратичная кривая поднимается быстрее. Это сравнение показывает закономерность, а не точное время выполнения конкретной программы.
| Тип алгоритма | Пример структуры | Примерное число действий | Как растёт при увеличении n |
|---|---|---|---|
| Последовательность действий без повторений | Несколько команд выполняются один раз | Постоянное число, например 5 | Не зависит от n, если число команд фиксировано |
| Один проход по n элементам | Цикл проверяет каждый элемент списка | Примерно n | Линейно: при увеличении n вдвое действий примерно вдвое больше |
| Два вложенных прохода по n элементам | Для каждого элемента просматривается весь список | Примерно n² | Квадратично: при увеличении n вдвое действий примерно вчетверо больше |
| Сравнение роста линейной и квадратичной сложности | Сопоставление одного и двух проходов | n и n² | Квадратичный рост становится быстрее при больших n |
Сначала найдите в таблице структуру, похожую на рассматриваемый алгоритм, а затем оцените число повторений. При сравнении подставляйте одинаковое n: так видно, насколько различаются затраты при одном и том же объёме данных. Таблица показывает примерный рост, поэтому не заменяет подсчёт конкретных команд.
Условие. Алгоритм просматривает список из n чисел и находит наибольшее. Сколько раз он обращается к элементам списка? Нужно отличать чтение элемента от остальных действий: нас спрашивают именно об обращениях.
Ответ. К элементам списка алгоритм обращается n раз; это один проход и линейный рост. Число сравнений может быть на единицу меньше, но оно тоже растёт пропорционально n. Разделение этих подсчётов полезно, потому что задача спрашивает обращения, а не все действия программы.
Условие. Для каждой пары элементов списка из n чисел алгоритм выполняет сравнение. Нужно определить, как зависит число сравнений от n. Важно выяснить, считается ли пара упорядоченной: если сравнивать элемент с самим собой и повторять пары в обратном порядке, подсчёт будет другим.
Ответ. При полном переборе пар число сравнений растёт пропорционально n². Точное количество зависит от того, включаются ли сравнения элемента с самим собой и повторные сравнения одной пары. Для оценки сложности достаточно установить, что вложенные проходы создают квадратичный рост.
Условие. Первый алгоритм выполняет примерно 5n действий, второй — примерно n². Какой выбрать для списка из 100 элементов и почему? Чтобы ответить, подставим один и тот же размер списка в обе оценки.
Ответ. Для списка из 100 элементов по указанным оценкам выбираем первый алгоритм: около 500 действий против примерно 10 000. Вывод относится к заданным приближённым оценкам; на практике могут влиять реализация и постоянные затраты. При выборе для больших списков особенно важен тип роста, а не только результат на маленьком примере.
Считать сложность точным временем выполнения. Секунды зависят от компьютера и реализации, поэтому одинаковая оценка не обещает одинаковой длительности. Эту путаницу допускают, потому что в обычных задачах скорость часто измеряют временем. Проверьте себя: выражена ли оценка через n и число действий, а не через секунды?
Считать любой цикл линейным. Число повторений зависит от границ цикла, а вложенность может умножить количество шагов. Ошибка возникает, если заметить слово «цикл», но не проследить, сколько раз выполняется его тело. Для проверки отдельно подсчитайте число повторений каждого цикла.
Принимать два вложенных прохода за 2n действий. Это было бы верно, если бы оба прохода просто выполнились один за другим. При вложенности внутренний проход повторяется для каждого элемента внешнего цикла, поэтому часто получается n × n = n². Проверьте, запускается ли внутренний цикл заново на каждом шаге внешнего.
Сравнивать алгоритмы только на маленьком примере. При небольшом n различие в росте может быть незаметным, а при увеличении списка быстро вырасти. Так происходит, потому что квадратичная оценка увеличивается быстрее линейной. Проверьте вывод, подставив несколько существенно больших значений n.
Для оценки сложности нужно уметь читать алгоритмы и программы с циклами, а также находить число повторений команд. Эти навыки позволяют перейти от записи программы к подсчёту действий через размер данных n. Оценка особенно полезна при работе с массивами, поиском и сортировкой: на маленьких наборах разные решения могут казаться одинаково быстрыми, но на больших данных затраты заметно расходятся.
Что именно называют сложностью алгоритма?
Это оценка того, как количество действий алгоритма зависит от размера входных данных. Она описывает характер роста затрат, а не точное время выполнения.
Почему время работы зависит не только от алгоритма?
На время влияют скорость компьютера, язык программирования и особенности реализации. Поэтому сложность сравнивает рост числа действий, а не секунды на конкретном устройстве.
Как определить число действий в цикле?
Нужно выяснить, сколько раз выполняется тело цикла, а затем оценить число действий за один проход. Если цикл проходит по всем n элементам и на каждом шаге делает постоянное число действий, рост будет линейным.
Почему два вложенных цикла часто дают квадратичную сложность?
Внутренний цикл выполняется для каждого шага внешнего. Если оба проходят примерно по n элементам, получается около n × n действий, то есть рост порядка n².
Как понять, какой из двух алгоритмов будет эффективнее на больших данных?
Нужно сравнить, как растёт число действий у каждого алгоритма при увеличении размера входных данных. Алгоритм с более медленным ростом обычно выгоднее на больших данных, даже если на маленьком примере разница незаметна.
§ 22. Сложность алгоритмов
