Структуры и алгоритмы обработки данных. Ключарев А.А - 9 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

9
Таблица 1
n log nnlog nn
2
100 1
16 4 64 256
256 8 2 048 65 536
4 096 12 49 152 16 777 216
65 536 16 1 048 565 4 294 967 296
1 048 476 20 20 969 520 1 099 301 922 576
16 775 616 24 402 614 784 281 421 292 179 456
Если считать, что числа соответствуют микросекундам, то для зада-
чи с 1048476 элементами алгоритму со временем работы T(log n) потре-
буется 20 микросекунд, а алгоритму со временем работы T(n
2
) – более
12 дней.
Если операция выполняется за фиксированное число шагов, не за-
висящее от количества данных, то принято писать O(1).
Следует обратить внимание, что основание логарифма здесь не пи-
шется. Причина этого весьма проста. Пусть есть O(log
2
n). Но log
2
n =
= log
3
n/log
3
2, а log
3
2, как и любую константу, символ О() не учитывает.
Таким образом, O(log
2
n) = O(log
3
n). К любому основанию можно перей-
ти аналогично, а значит, и писать его не имеет смысла.
Практически время выполнения алгоритма зависит не только от ко-
личества входных данных, но и от их значений, например, время рабо-
ты некоторых алгоритмов сортировки значительно сокращается, если
первоначально данные частично упорядочены, тогда как другие методы
оказываются нечувствительными к этому свойству. Чтобы учитывать
этот факт, полностью сохраняя при этом возможность анализировать
алгоритмы независимо от данных, различают:
– максимальную сложность T
max
(n), или сложность наиболее небла-
гоприятного случая, когда алгоритм работает дольше всего;
– среднюю сложность T
mid
(n) – сложность алгоритма в среднем;
– минимальную сложность T
min
(n) – сложность в наиболее благо-
приятном случае, когда алгоритм справляется быстрее всего.
Теоретическая оценка временной сложности алгоритма осуществля-
ется с использованием следующих базовых принципов:
1) время выполнения операций присваивания, чтения, записи обычно
имеют порядок O(1). Исключением являются операторы присваивания, в
которых операнды представляют собой массивы или вызовы функций;

Страницы