Page 95 - Bkhargava_-_Grokaem_algoritmy

94 Глава 4. Быстрая сортировка

Перед вьrводом элемента функция делает паузу продолжительностью
в 1 секунду. Предположим, вы выводите список из пяти элементов с ис­
пользованием обеих функций:

! 2 f 4 / 6 1 ~ ! 10]
~
f .,..;~tдe.l'ls : 2 +6 <а 1 \6

pri"t_ite1»s2: <ПАУ.3А> 2 <ПАУ.3А> 4<ПАУ.3А> 6 <ПАУ.3А> i <ПАУ.3А> 1\li

Обе функции проходят по списку один раз, и обе выполняются за вре­
мя О(п). Как вы думаете, какая из них работает быстрее? Я думаю, print_
i tems работает намного быстрее, потому что она не делает паузу перед вы­
водом каждого элемента. Следовательно, даже при том, что обе функции
имеют одинаковую скорость «О-большое~, реально print_i tems работает
быстрее. Когда вы используете «О-большое~ (например, О(п)), в действи­
тельности это означает следующее:

C*h

ФИКСИРО6АННЫ~ _j"
ПРОМ~УТОК
ВРЕМЕНИ

Здесь с - некоторый фиксированный промежуток времени для вашего
алгоритма. Он называется константой. Например, время выполнения
может составлять 10 мWULисекунд * п для print_i tems против 1 секунды * п
для print_i tems2.

Обычно константа игнорируется, потому что если два алгоритма имеют
разное время «О-большое~, она роли не играет. Для примера возьмем би­
нарный и простой поиск. Допустим, такие константы присутствуют в обоих
алгоритмах.

1 с.* Lo~ n
n l'OCTO~ ПОИСК БИНА l'Hbl~ ПОИСК

www.trk.kg