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

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

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

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

Некоторые определения сложности в справочном руководстве С++ названы амортизируемыми. Это означает, что в долгосрочной перспективе эти операции

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

Общие концепции

в этой главе описаны основополагающие концепции стандартной библиотеки С++, необходимые для работы со всеми ее компонентами:

О пространство имен std;

О имена и форматы заголовочных файлов;

О общие принципы обработки ошибок и исключений;

О знакомство с распределителями памяти.

Пространство имен std

При использовании модулей и/или библиотек всегда существует вероятность конфликтов имен, которые возникают из-за того, что в модулях и библиотеках один и тот же идентификатор может применяться для разных целей. Для решения этой проблемы в С++ поддерживается концепция пространств имен (см. с. 32). Пространство имен определяет область видимости идентификаторов. В отличие от классов пространства имен открыты для расширений, определяемых в любых источниках. Таким образом, в пространстве имен могут определяться компоненты, распределенные по нескольким физическим модулям. Характерным примером такого компонента является стандартная библиотека С++, поэтому вполне логично, что в ней используется пространство имен. Все идентификаторы стандартной библиотеки С++ определяются в пространстве имен с именем std.

В соответствии с концепцией пространств имен существуют три варианта использования идентификаторов из стандартной библиотеки С++.

О Непосредственное уточнение идентификатора (например, полная запись std::ostream вместо ostream). В этом варианте записи полная команда вывода может выглядеть так:

stc(::cout std::hex 3.4 std;;endl;

О Использование объявления using (см. с, 33). Например, следующий фрагмент предоставляет локальную возможность пропуска префикса std:: для cout и endl:

using std::cout: using std:lendl: