Лекции по программированию. Основные понятия классификация программного обеспечения

• Название: Основные понятия классификация программного обеспечения
• Анкор: Лекции по программированию.doc
• Дата: 15.01.2018
• Размер: 1.57 Mb.
• Имя файла: Лекции по программированию.doc
• Тип: Документы; #14117
• Категория: Информатика. Вычислительная техника
• страница: 6 из 6

6.3. АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА

Этот алгоритм решает задачу поиска в списке некоторо­го заданного значения. Он позволяет установить, есть ли заданное значение в списке. Если это значение в списке присутствует, поиск будет считаться успешным, в противном случае - неудачным.

При этом считается, что список отсортирован согласно некото­рому правилу, позволяющему упорядочить его элементы. Например, если это список имен, то имена в нем расположены в алфавитном порядке. Если же это список числовых значений, то его элементы расположены в порядке возрастания. В результате получается про­цедура, текст которой приведен ниже.

procedure Поиск (<список>, <искомое значение>) if (список пуст)

then (объявить поиск неудачным)

else

(выбрать как <проверяемое значение> первый

элемент списка)

while (<искомое значение> > <проверяемое значение> и есть непроверенные элементы) do (выбрать следующий элемент списка как <проверяемое значение>) if (<искомое значение> = <проверяемое значение>)

then (объявить поиск успешным) else (объявить поиск неудачным)

По окончании выполнения структуры while искомое значение либо будет найдено, либо выяснится, что его нет в списке. В любом случае успешность поиска можно установить, сравнивая искомое значение с проверяемым. Если они эквивалентны, поиск объявля­ется успешным. Для полной уверенности в правильности програм­мы она помещается в предложение else инструкции if.

Такая процедура позволяет установить, является ли кто-то пас­сажиром некоторого рейса, или установить, входит ли сахар в пе­речень ингредиентов некоторого блюда.

Таким образом, алгоритм последовательно рассматривает все элементы списка. В силу своей простоты он часто применяется к коротким спискам или когда это необходимо. Однако в случае длинных списков этот метод оказывается менее эффективным, чем другие.

6.4. АЛГОРИТМ ДВОИЧНОГО ПОИСКА

Также решает задачу поиска заданного элемента в от­сортированном списке. Здесь используется процедура, которую человек использует при поиске имени в телефонном справочнике. Справочник открывается примерно в том месте, где может нахо­диться нужное имя. Если повезет, оно окажется именно там, в про­тивном случае поиск придется продолжить. Однако в этой точке область поиска сужается либо до начальной части справочника, предшествующей текущей позиции, либо до остальной части спра­вочника, следующей за ней.

Реализовать эту стратегию можно с помощью следующего алго­ритма, в котором учитывается возможность получения пустого списка.

procedure Search (<список>, <искомое_значение>) if (<список> пуст)

then (Объявить поиск неудачным)

else

(Выбрать "средний" элемент в <список> в качестве

<проверяемый_элемент>)

(Выполнить один из следующих трех блоков инструкций, в зависимости от того, является ли <искомое значение> равным, меньшим или большим, чем <проверяемый элемент>)

Case 1: <искомое_значение> = <проверяемый_элемент> (Объявить поиск успешным)

Case 2: <искомое_значение> < <проверяемый_элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, предшествующей элементу <проверяемый элемент>, элемент <искомое_значение>, и if (тот поиск успешен

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным) Case 3: <искомое_значение> > <проверяемый__элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, следующей за элементом <проверяемый_элемент>, элемент <искомое_значение> и if (тот поиск успешен)

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным)

Если выбранный элемент не является искомым, то эта программа предлагает два варианта дальнейших действий - поиск в начальной или конечной половине списка. В каждом из них предусматривается выполнение вторичного поиска той же процедурой Search.

При выполнении этой процедуры и при достижении инструкции <Применить процедуру Search, чтобы ...>, будет применяться этот же метод поиска к меньшему списку, который является частью исходного списка. Если этот вторичный поиск завершится успешно, то осуществляется возврат в исходную процедуру, чтобы объявить выполняемый в ней поиск успешным. Если же вторичный поиск окончится неудачей, то объявляется неудачным и исходный поиск.

В этом процессе необходимо многократно разделять рассмат­риваемый список на две примерно равные части, после чего об­ласть дальнейшего поиска ограничивается лишь одной из этих час­тей. За это повторяющееся деление на два данный алгоритм был назван двоичным поиском.

Алгоритм двоичного поиска похож на алгоритм последователь­ного поиска, так как в обоих выполняется повторяющийся процесс. Однако реализация этого повторения в каждом случае существенно отличается. При последовательном поиске повторение организует­ся с помощью цикла, в случае двоичного поиска каждая стадия по­вторения реализуется как подзадача предыдущей стадии. Этот ме­тод повторения известен как рекурсия.
6.5. АЛГОРИТМ СОРТИРОВКИ МЕТОДОМ ВСТАВКИ

В этом алгоритме решается задача сортировки списка имен в алфавитном порядке. При этом необходимо отсортировать список путем перестановки его элементов, не перемещая весь спи­сок в другое место. Подобное ограничение типично для компью­терных приложений, где стремятся наиболее эффективно исполь­зовать весь доступный объем памяти.

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

procedure Сортировка (<список>) assign N the value 2;

while (значение N не превышает <длина списка>)

do (Выбрать N-й элемент списка в качестве опорного; Переместить этот элемент во временное хранилище, оставив в списке пустое место;

while (над пустым местом есть имя, которое по алфавиту размещается ниже, чем опорный элемент)

do (переместить имя, находящееся над пустым местом вниз, оставив в прежней позиции пустое место); Поместить опорный элемент на пустое место в списке assign Nthe value N+1

здесь N - счетчик, параметр <длина списка> - количество эле­ментов в списке.

Программа сортирует список, многократно повторяя следую­щие действия: «Элемент извлекается из списка, а затем вставляется на надлежащее ему место».

Каждое выполнение тела внешнего цикла приводит к тому, что внутренний цикл инициализируется и выполняется до тех пор, пока не будет выполнено условие его окончания. Условие окончания внешнего цикла выполняется, когда значение счетчика N превысит длину сортируемого списка.

Управление внутренним циклом инициализируется, когда опорный элемент извлекается из списка и в нем образуется пустое место. Операция модификации включает перемещение располо­женных выше элементов на пустое место вниз, в результате чего свободное место перемещается вверх по списку. Условие оконча­ния выполняется, когда пустое место или находится непосредст­венно под именем, которое по алфавиту размещается выше опор­ного значения или же достигает верхней позиции списка.

6.6. ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ

Современные вычислительные машины способны вы­полнять миллионы операций в секунду, однако эффективность по-прежнему остается важнейшим аспектом разработки алгоритмов. Часто выбор между эффективным и неэффективным решением за­дачи может на самом деле означать выбор между реализуемым и нереализуемым способом ее решения.

Рассмотрим задачу, с которой сталкивается секретарь универ­ситета при поиске личных дел студентов и их заполнении. В уни­верситете на протяжении любого семестра числится около 30 ты­сяч студентов. Чтобы найти личное дело некоторого студента, сек­ретарь должен выполнить поиск по его идентификационному номеру в общем списке. Почувствует ли секретарь разницу при по­иске между алгоритмом последовательного и двоичного поиска?

Алгоритм последовательного поиска начинает работу с начала списка и последовательно сравнивает каждый выбираемый элемент с искомым числом. Средняя глубина поиска будет равна половине длины списка из 15-ти тысяч элементов. Если выборка каждого де­ла из памяти выполняется за 10 мс, то среднее время поиска будет составлять 150 секунд. Этот вариант совершенно неприемлем.

Алгоритм двоичного поиска сравнивает искомое значение со средним элементом списка. Если это не искомый элемент, то об­ласть поиска сразу же сужается до половины исходного списка. После второго этапа область поиска в большинстве случаев сокра­тится до 7 500 дел и т. д. Искомое значение будет найдено при вы­боре, максимум 15 элементов списка. Процесс поиска нужного личного дела потребует не более 0,15 секунды, то есть мгновенно.

В общем случае такой анализ осуществляется в более широком контексте. Хотя выше рассматривался список определенной длины, эти рассуждения можно обобщить на случай списка произвольной длины. При применении к списку из п элементов алгоритма после­довательного поиска в среднем потребуется проверить п/2 элемен­тов, тогда как алгоритму двоичного поиска, в самом худшем случае, потребуется проверить только log₂nэлементов (логарифм по­казывает, сколько раз число п можно разделить на два).

Аналогичным образом можно проанализировать алгоритм сор­тировки методом вставки. Поскольку основным действием в реали­зации этого алгоритма является сравнение двух имен, то необхо­димо подсчитать количества таких сравнений, которые потребуется выполнить при сортировке списка длиной п элементов.

В наилучшем случае применение алгоритма сортировки мето­дом вставки к списку из п элементов потребует выполнения n-1 сравнений. (Второй элемент сравнивается с одним элементом (пер­вым), третий элемент — с одним элементом (вторым) и т. д.)

Наихудший сценарий имеет место в том случае, когда каждый опорный элемент потребуется сравнивать со всеми впереди стоя­щими элементами. Первый опорный элемент (второй элемент спи­ска) сравнивается с одним элементом, второй опорный элемент (третий элемент списка) - с двумя элементами и т. д. Следователь­но, общее количество сравнений при сортировке списка из п эле­ментов составит 1 + 2 + 3 + ... + (n - 1), что эквивалентно п(п-1)/2 или (1/2)(n² - п).

В среднем при сортировке методом вставки можно ожидать, что каждый опорный элемент потребуется сравнить с половиной предшествующих ему элементов. В этом случае общее количество выполненных сравнений будет вдвое меньше, т. е. (1/4)(n2 — п).


Количество сравнений, выполненных алгоритмом сортировки методом встав­ки, позволяет оценить вре­мя, которое потребуется для выполнения сортиров­ки. Эта оценка показана на графике (рис. 6), который построен по оценкам рабо­ты алгоритма в наихудшем случае, когда для списка длиной п требуется выпол­нить не менее (1/2)(n²-n) сравнений элементов. При увеличении длины списка на одно и то же количество элементов время, необХОДИМОЕ ДЛЯ СОрТИрОВКИ списка, все больше и больше возрастает. Та­ким образом, с увеличе­нием длины списка эф­фективность данного ал­горитма уменьшается.

При использовании алгоритма двоичного по­иска в наихудшем слу­чае для поиска в списке из п элементов потребу­ется проанализировать не более log₂nэлемен­тов. На рис. 7 представлен график, построенный по результатам ана­лиза времени, необходимого для выполнения алгоритма при различ­ной длине сортируемого списка. Темпы роста времени выполнения алгоритма снижаются по мере увеличения длины списка, т. е. эф­фективность алгоритма двоичного поиска возрастает с увеличением длины списка.

Основным отличием между этими графиками является их общая форма, которая определяется типом отображаемого выражения. Все линейные выражения изображаются прямой линией, все квадратич­ные выражения - параболической кривой, а все логарифмические выражения порождают логарифмическую кривую.

Форма графика, представляющего зависимость времени выпол­нения алгоритма от объема входных данных, отражает общие ха­рактеристики эффективности алгоритма. Поэтому алгоритмы при­нято классифицировать согласно форме их графиков, построенных для самого неблагоприятного случая.

Способ обозначения, используемый для определения этих классов, иногда называют тета-классами. Алгоритмы, графики которых имеют параболическую форму (например, сортировка методом вставки), относятся к классу Θ (n²), алгоритмы, графики которых имеют логарифмическую форму (например, двоичный поиск), - к классу Θ (lg п). Таким образом, любой алгоритм из тета-класса Θ (lgn) по самой свой сути всегда более эффективен, чем алгоритм из тета-класса Θ (п²).