Page 56 - Bkhargava_-_Grokaem_algoritmy

Сортировка выбором 55

Продолжая действовать так, мы получаем отсортированный список.

.... п~ С:ЧЕ.ТЧМIС. &ОС-
ПPOMJ&EJlE.HИA
!t.ADIOl-\EAD 156
Kl.Sl-\01\~ KUMAR 14-1
\./ILCO 111
N~UTRAL MILK 1-\0T~L 94-

ЬЕСК ~&
TI-\~ .STROK~.S 61
TI-\~ ЫАСК KfY.S 35

А теперь попробуем оценить происходящее с точки зрения теории вычис­
лений и посмотрим, сколько времени будут занимать операции. Напомним,
что время О(п) означает, что вы по одному разу обращаетесь к каждому
элементу списка. Например, прИ: простом поиске по списку исполнителей
каждый исполнитель будет проверен один раз.

1. RADIOHEAD
2.. KI.SHOP.E KUMAP.
3. ТНЕ ЬLАСК KEY.S 1'\
элеменW108
't. HEUTP.AL MILK HOTEL
5. ЬЕСК
б. ТНЕ STP.OKJ;;S

1-. \.JILCO

Чтобы найти исполнителя с наибольшим значением счетчика воспроиз­
ведения, необходимо проверить каждый элемент в списке. Как вы уже
видели, это делается за время О(п). Итак, имеется операция, выполняемая
за время О( п ), и ее необходимо выполнить п раз:

www.trk.kg