ВУЗ:
них всегда нужно помнить при самостоятельной разработке алгоритмов. Первое из них – эффективность, а второе – пра-
вильность.
Эффективность алгоритма. Хотя современные машины способны выполнять миллионы операций в секунду, эффек-
тивность по-прежнему остается важнейшим аспектом разработки алгоритмов. Зачастую выбор между эффективным и неэф-
фективным решением задачи может на самом деле означать выбор между реализуемым и нереализуемым способом ее реше-
ния.
Рассмотрим задачу, с которой сталкивается секретарь университета при поиске личных дел студентов и их заполнении.
Хотя в университете на протяжении любого семестра фактически числится около 10 000 студентов, секретарю в действи-
тельности приходится иметь дело с более чем 30 000 личных дел, поскольку за несколько предыдущих лет многие из студен-
тов зарегистрировались для изучения хотя бы одной из преподаваемых в университете дисциплин, но не смогли закончить
цикл обучения. Теперь предположим, что все личные дела хранятся в компьютере секретаря в виде списка, упорядоченного
по идентификационным номерам каждого из студентов. Чтобы найти личное дело некоторого студента, секретарь должен
выполнить поиск по его идентификационному номеру в общем списке.
Мы уже познакомились с двумя алгоритмами поиска в подобных списках последовательным и двоичным поиском.
Сейчас нам нужно дать ответ на вопрос, почувствует ли секретарь разницу между этими двумя алгоритмами? Начнем с рассмот-
рения последовательного поиска.
При заданном идентификационном номере студента алгоритм последовательного поиска начинает работу с начала спи-
ска и последовательно сравнивает каждый выбираемый элемент с искомым числом. Не зная, что представляет собой искомое
число, мы не можем определить, насколько далеко потребуется просматривать список. Все же можно утверждать, что для
множества выполненных операций поиска их средняя глубина будет равна приблизительно половине длины списка, хотя в
отдельных случаях поиск потребует меньшего числа операций, а в других – большего. Можно сделать вывод, что при много-
кратном выполнении последовательного поиска на каждый случай в среднем приходится приблизительно 15 000 просмот-
ренных личных дел. Если выборка каждого личного дела из памяти и сравнение его номера с искомым выполняется за де-
сять миллисекунд (десять тысячных долей секунды), то среднее время поиска будет составлять 150 с или две с половиной
минуты. Если секретарю придется так долго ожидать появления на экране монитора личного дела интересующего его сту-
дента, несомненно, что этот вариант совершенно неприемлем. Даже если время выборки и проверки каждой записи сокра-
тить до одной миллисекунды, на поиск личного дела студента все равно потребуется в среднем около 15 с – все еще слиш-
ком много для среднего времени ожидания ответа, которое можно считать приемлемым.
В противоположность этому, алгоритм двоичного поиска начинает работу со сравнения искомого значения со средним
элементом списка. Если это не искомый элемент, то область поиска сразу же сужается до половины исходного списка, т.е.
после проверки среднего элемента списка из 30 000 личных дел алгоритм двоичного поиска в большинстве случаев выберет
для дальнейшего рассмотрения только 15 000 дел. После второго этапа область поиска в большинстве случаев сократится до
7500 дел, после третьего – до 3750 и т.д. В результате искомое значение будет найдено при выборе, самое большее, 15 эле-
ментов списка, состоящего из 30 000 дел. Таким образом, если каждое выбранное значение обрабатывается за 10 миллисе-
кунд, процесс поиска нужного личного дела потребует не более 0,15 с, а это означает, что с точки зрения секретаря личное
дело любого студента будет появляться на экране практически мгновенно. Можно сделать обоснованное заключение, что
выбор между алгоритмом последовательного поиска и алгоритмом двоичного поиска в данном случае имеет большое значе-
ние
2
.
Этот пример иллюстрирует важность той области компьютерных наук, которую называют анализом алгоритмов. Эта
область связана с изучением необходимых алгоритмам ресурсов, таких, как время или используемый объем памяти. Основ-
ным практическим применением результатов подобных исследований является оценка относительных достоинств альтерна-
тивных алгоритмов. В нашем случае мы проанализировали время, требующееся алгоритмам последовательного и двоичного
поиска, что позволило нам определить, какой из них больше подходит в данном конкретном случае. В общем случае такой
анализ осуществляется в более широком контексте. Это означает, что при рассмотрении алгоритмов, выполняющих поиск в
списке, мы не ограничимся списком фиксированной длины, но пытаемся вывести формулу эффективности алгоритма для
списков произвольной длины. Такой анализ включает изучение ситуаций, в которых алгоритм демонстрирует свои наилуч-
шие свойства, ситуаций, когда его эффективность минимальна, а также оценку его средней производительности.
В предыдущем случае выполненный нами анализ заключался в оценке средней производительности алгоритма после-
довательного поиска, а также определении той производительности, которую алгоритм двоичного поиска продемонстрирует
в наихудшем случае. Хотя мы рассматривали список определенной длины, несложно обобщить наши рассуждения на случай
списка произвольной длины. В частности, при применении к списку из п элементов алгоритму последовательного поиска в
среднем потребуется проверить n/2 элементов, тогда как алгоритму двоичного поиска в самом худшем случае потребуется
проверить только log
2
n элементов. (В данном случае выражение log
2
n представляет логарифм числа п по основанию 2, кото-
рый показывает, сколько раз число n можно разделить на два.)
Давайте попробуем проанализировать аналогичным образом алгоритм сортировки методом вставки. Поскольку основ-
ным действием в реализации данного алгоритма является сравнение двух имен, наш подход будет состоять в подсчете коли-
чества таких сравнений, которые потребуется выполнить при сортировке списка длиной п элементов.
Вспомним, что при сортировке методом вставки осуществляется выбор некоторого элемента, называемого опорным;
после этого он сравнивается с предшествующими ему элементами, пока для него не будет найдено надлежащее место, после
чего опорный элемент вставляется в соответствующую позицию. Алгоритм начинается с выбора второго элемента списка в
качестве опорного. По мере его выполнения в качестве опорных выбираются следующие элементы – пока не будет достиг-
2
Чтобы воспользоваться преимуществами алгоритма двоичного поиска, личные дела студентов должны располагаться в памяти машины
таким образом, чтобы можно было извлекать средние записи последовательно уменьшающихся подсписков без чрезмерных усилий. Это можно
осуществить, запоминая личные дела в индексированных файлах-структурах, которые будут обсуждаться в главе 8. Кроме того, тех же результа-
тов можно достичь и с использованием хешированных файловых структур, которые также описываются в главе 8.
Страницы
- « первая
- ‹ предыдущая
- …
- 96
- 97
- 98
- 99
- 100
- …
- следующая ›
- последняя »
