На этом шаге мы рассмотрим понятие сложности алгоритмов.
В некоторых компонентах стандартной библиотеки C++ (и особенно в STL) первостепенное внимание уделяется скорости работы алгоритмов и функций классов. По этой причине в стандарт включены требования к их "сложности". Специалисты по информатике применяют специальную систему обозначений для сравнения относительной сложности алгоритмов. По этому критерию можно быстро оценить относительное время работы алгоритма, а также сравнить алгоритмы на качественном уровне. Эта система обозначений называется О-записъю.
О-запись выражает время работы алгоритма как функцию от объема входных данных n. Например, если время работы алгоритма прямо пропорционально количеству элементов (удвоение объема входных данных в два раза увеличивает время работы), сложность алгоритма записывается в виде О(n). Если время работы не зависит от объема входных данных, алгоритм обладает сложностью O(1). В таблице 1 перечислены типичные варианты сложности и соответствующая им О-запись.
| Тип | Обозначение | Описание |
|---|---|---|
| Постоянная сложность | O(1) | Время работы не зависит от количества элементов |
| Логарифмическая сложность | O(log(n)) | Время работы возрастает в логарифмической зависимости от количества элементов |
| Линейная сложность | O(n) | Время работы возрастает прямо пропорционально количеству элементов |
| Сложность n-log-n | O(n*log(n)) | Время работы возрастает как произведение линейной и логарифмической зависимостей от количества элементов |
| Квадратичная сложность | O(n2) | Время работы возрастает в квадратичной зависимости от количества элементов |
Необходимо помнить, что О-запись скрывает менее значимые факторы (например, постоянные затраты времени). Фактическое время работы алгоритма в расчет не принимается; любые два линейных алгоритма считаются эквивалентными. Возможны даже ситуации, когда константа в линейном алгоритме оказывается настолько огромной, что на практике предпочтение может отдаваться экспоненциальному алгоритму с малой константой. Впрочем, О-запись не претендует на совершенство. Просто помните, что она лишь приблизительно характеризует алгоритм, а алгоритм с оптимальной сложностью не всегда является лучшим.
В таблице 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, необходимые для работы со всеми ее компонентами.
