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

   
На этом шаге мы рассмотрим понятие сложности алгоритмов.

   
В некоторых компонентах стандартной библиотеки C++ (и особенно в STL) первостепенное внимание
уделяется скорости работы алгоритмов и функций классов. По этой причине в стандарт включены требования к их
"сложности". Специалисты по информатике применяют специальную систему обозначений для сравнения
относительной сложности алгоритмов. По этому критерию можно быстро оценить относительное время работы алгоритма,
а также сравнить алгоритмы на качественном уровне. Эта система обозначений называется О-записъю.

   
О-запись выражает время работы алгоритма как функцию от объема входных данных n. Например, если время
работы алгоритма прямо пропорционально количеству элементов (удвоение объема входных данных в два раза
увеличивает время работы), сложность алгоритма записывается в виде О(n). Если время работы не зависит от
объема входных данных, алгоритм обладает сложностью O(1). В таблице 1 перечислены типичные варианты
сложности и соответствующая им О-запись.

Таблица 1. Типичные варианты сложности

Тип Обозначение Описание
Постоянная сложность O(1) Время работы не зависит от количества элементов
Логарифмическая сложность O(log(n)) Время работы возрастает в логарифмической зависимости от количества элементов
Линейная сложность O(n) Время работы возрастает прямо пропорционально количеству элементов
Сложность n-log-n O(n*log(n)) Время работы возрастает как произведение линейной и логарифмической зависимостей от количества элементов
Квадратичная сложность O(n2) Время работы возрастает в квадратичной зависимости от количества элементов

   
Необходимо помнить, что О-запись скрывает менее значимые факторы (например, постоянные затраты времени).
Фактическое время работы алгоритма в расчет не принимается; любые два линейных алгоритма считаются эквивалентными.
Возможны даже ситуации, когда константа в линейном алгоритме оказывается настолько огромной, что на практике
предпочтение может отдаваться экспоненциальному алгоритму с малой константой. Впрочем, О-запись не
претендует на совершенство. Просто помните, что она лишь приблизительно характеризует алгоритм, а алгоритм с
оптимальной сложностью не всегда является лучшим.

   
В таблице 2 приведены примеры с разными количествами элементов, которые дают представление о темпах увеличения
времени работы. Как видите, при малом количестве элементов значения времени работы почти не различаются. Именно
здесь постоянные затраты времени, скрытые в О-записи, вносят наиболее существенный вклад. Но с ростом
количества элементов различия начинают проявляться более заметно, а постоянные факторы уходят на второй план.
Помните, что при оценке сложности алгоритмов необходимо мыслить масштабно, не ограничиваясь простейшими закономерностями.

Таблица 2. Относительное время работы алгоритма в зависимости от типа и количества элементов

Тип Обозначение 1 2 5 10 50 100 1000
Постоянная сложность O(1) 1 1 1 1 1 1 1
Логарифмическая сложность O(log(n)) 1 2 3 4 6 7 10
Линейная сложность O(n) 1 2 5 10 50 100 1000
Сложность n-log-n O(n*log(n)) 1 4 15 40 300 700 10000
Квадратичная сложность O(n2) 1 4 25 100 2500 10000 1000000

   
Некоторые определения сложности в справочном руководстве C++ названы амортизируемыми.
Это означает, что в долгосрочной перспективе эти операции ведут себя так, как описано. С другой стороны, единичные
операции могут занимать больше времени. Например, время присоединения элементов к динамическому массиву
зависит от того, хватает ли в массиве памяти для очередного элемента. Если памяти достаточно, то операция выполняется
с постоянным временем, потому что вставка нового последнего элемента не зависит от размера массива. Но если
памяти не хватает, то операция выполняется с линейной сложностью, поскольку для нее приходится выделять новый
блок памяти и копировать все элементы. Однако перераспределение памяти происходит относительно редко, поэтому
достаточно длинная последовательность операций ведет себя так, как если бы каждая операция выполнялась с
постоянной сложностью. Таким образом, вставка характеризуется амортизируемой постоянной сложностью.

   
Начиная со следующего шага, мы рассмотрим основополагающие концепции стандартной библиотеки
С++, в которую входит библиотека STL, необходимые для работы со всеми ее компонентами.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий