Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 1. Основные понятия

end;

В главе 5 вы найдете более подробную информацию о рекурсивных алгоритмах.

j

Средний и наихудший случай

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

function LocateItem(target : Integer) : Integer;

var

i : Integer;

begin

for i := 1 to N do

if (Value[i]=target) then

begin

Result := i; break; end;

end;

Если искомый элемент находится в конце списка, то программе придется ис­следовать все N элементов списка, чтобы обнаружить нужный. Это займет ty ша­гов, и сложность алгоритма будет равна O(N). В данном, так называемом наихуд­шем случае (worst case) время работы алгоритма будет максимальным.

С другой стороны, если искомый число расположено в самом начале Списка, алгоритм завершит работу почти сразу же. Он выполнит несколько шагов, прежде чем найдет искомый номер и остановится. Это наилучший случай (best case) со сложностью порядка 0(1). Строго говоря, подобный случай не очень интересен, поскольку он вряд ли произойдет в реальной жизни. Интерес представляет сред­ний или ожидаемый вариант (expected case) поведения алгоритма.

Если номера элементов в списке изначально беспорядочно смешаны, то иско­мый элемент может оказаться в любом месте списка. В среднем потребуется ис­следовать N/2 элементов для того, чтобы найти требуемый. Значит, сложность это­го алгоритма в усредненном случае будет порядка 0(N/2), или O(N), если убрать постоянный множитель.

Для некоторых алгоритмов наихудший случай сильно отличается от ожидаемо­го случая. Например, алгоритм быстрой сортировки, описанный в главе 9, имеет наихудший случай поведения 0(№), а ожидаемое поведение равно 0(N * log(N)), что гораздо быстрее. Алгоритмы, подобные алгоритму быстрой сортировки, иногда делают очень длинными, чтобы исключить возникновение наихудшего случая по­ведения.

Общие функции оценки сложности

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

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.