Алгоритмы неформально. Инструкция для начинающих питонистов - [34]

Если бы нам потребовалось выразить время выполнения спящей сортировки в нотации «О большое», оно составит O(max(list)). В отличие от времени выполнения всех известных алгоритмов сортировки, его время выполнения зависит не только от размера списка, но и от размера элементов списка. Все это делает спящую сортировку слишком ненадежной, поскольку можно быть уверенным в ее быстродействии только с конкретными списками — даже короткий список с очень большими элементами может потребовать слишком много времени.

Никаких причин для практического применения спящей сортировки быть не может, даже на тонущем корабле. Я включил ее в книгу по нескольким причинам. Во-первых, из-за того что она так сильно отличается от других популярных алгоритмов сортировки, это напоминает нам, что даже в самых изученных и статичных областях исследования остается место для творческого подхода и инноваций, и это открывает новую точку зрения на то, что казалось узкой и специализированной темой. Во-вторых, поскольку этот алгоритм был разработан и опубликован анонимно, а его создатель, вероятно, не принадлежит к числу известных исследователей, это напоминает нам, что великие мысли и гении могут встречаться не только в новомодных университетах и ведущих фирмах, но и среди нас, непризнанных и не пользующихся авторитетом. В-третьих, алгоритм представляет замечательное новое поколение алгоритмов, предназначенных для использования на компьютере, — в том смысле, что такие алгоритмы не моделируют нечто такое, что можно сделать руками, как старые алгоритмы, а на фундаментальном уровне зависят от уникальных возможностей компьютеров (в данном случае приостановка выполнения и многопоточность). В-четвертых, компьютерные идеи, на которых базируется алгоритм (приостановка и многопоточность) чрезвычайно полезны и заслуживают место в инструментарии любого специалиста по алгоритмам как возможная основа для разработки других алгоритмов. Наконец, я питаю необъяснимую слабость к этому алгоритму — то ли из-за присущего ему странного проявления творческого подхода, то ли потому, что мне нравится механизм самоорганизующегося упорядочения элементов.

От сортировки к поиску

Поиск, как и сортировка, играет фундаментальную роль во многих задачах из информатики (и в жизни вообще). Допустим, вы хотите найти имя в телефонном справочнике или (раз уж мы живем в XXI веке) обратиться к базе данных и найти интересующую вас запись.

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

Бинарный поиск

Бинарный поиск — простой и эффективный метод поиска элементов в отсортированном списке. Он немного напоминает игру «угадай число». Допустим, кто-то задумал число от 1 до 100, и вы пытаетесь его отгадать. При первой попытке вы называете 50. Это неправильный ответ, но вам дают подсказку: загаданное число меньше 50. Вы называете число 49. Снова неправильно — загаданное число меньше 49. Вы называете 48, потом 47 и т.д., пока не придете к правильному ответу. Но это займет слишком много времени — если было загадано число 1, то вам потребуется 50 предположений, а это слишком много, поскольку возможны всего 100 вариантов.

Правильнее будет увеличить расстояние при следующем предположении. Если число 50 слишком велико, то подумайте, что можно узнать, если предположить 40 вместо 49. Если число 40 слишком мало, то мы исключаем 39 возможностей (1–39), и ответ гарантированно можно будет угадать за 9 предположений (41–49). Если число 40 слишком велико, то исключаются 9 возможностей (41–49), и ответ гарантированно можно будет указать за 39 предположений (1–39). Таким образом, выбор числа 40 сокращает количество вариантов с 49 (1–49) до 39 (1–39) в худшем случае. С другой стороны, выбор числа 49 сокращает количество вариантов с 49 (1–49) до 48 (1–48) в худшем случае. Очевидно, выбор числа 40 является более эффективной стратегией поиска, чем выбор 49.

Как выясняется, лучшая стратегия поиска основана на предположении ровно на середине диапазона остающихся возможностей. Если вы поступите подобным образом, а потом проверите, было ли ваше предположение слишком большим или малым, то всегда сможете исключить половину оставшихся вариантов. Исключая половину вариантов при каждом предположении, можно найти нужное значение достаточно быстро (O(log(n)) для тех, кто предпочитает более точные оценки. Например, в списке из 1000 элементов для нахождения любого элемента методом бинарного поиска хватит всего десяти предположений. Если разрешить 20 предположений, то можно правильно определить позицию элемента в списке, содержащем более миллиона элементов. Кстати говоря, именно так пишутся приложения-«угадайки», способные правильно «прочитать ваши мысли» всего за 20 вопросов.

Чтобы реализовать этот алгоритм на Python, для начала следует определить верхнюю и нижнюю границы для позиции, которую может занимать папка на полке. Нижняя граница равна 0, а верхняя определяется длиной полки:

sorted_cabinet = [1,2,3,4,5]