Программирование >>  Операторы преобразования типа 

1 ... 4 5 6 [ 7 ] 8 9 10 ... 239


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

Обозначение

Описание

Постоянная сложность

0(1)

Время работы не зависит от количества элементов

Логарифмическая сложность

0(log(n))

Время работы возрастает в логарифмической зависимости от количества элементов

Линейная сложность

0(п)

Время работы возрастает прямо пропорционально количеству элементов

Сложность n-log-n

0(n*log(n))

Время работы возрастает как произведение линейной и логарифмической зависимостей от количества злементов

Квадратичная сложность

Время работы возрастает в квадратичной зависимости от количества элементов

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

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

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

Обозначение ]

L 2

1000

Постоянная сложность

0(1) 3

Логарифмическая сложность

0(log(n)) ]

L 2

Линейная сложность

0(п) ]

L 2

1000

Сложность n-log-n

0(n*Iog(n)) 3

10 ООО

Квадратичная сложность

О(п) 3

2500

10 ООО

1000 ООО

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



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



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

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

О пространство имен 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:



1 ... 4 5 6 [ 7 ] 8 9 10 ... 239

© 2006 - 2022 pmbk.ru. Генерация страницы: 0
При копировании материалов приветствуются ссылки.
Яндекс.Метрика