Род Стивенс

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

end;

procedure Fast; var

i, j : Integer; begin

for i := 1 to N do for j := 1 to N do

Slow; // Вызов процедуры Slow.

end;

procedure RunBoth; begin

Fast ; end;

С другой стороны, если основная программа вызывает процедуры отдельно, их вычислительная сложность складывается. В этом случае итоговая сложность по порядку величины равна 0(№) + 0(№) = 0(N3). Следующий фрагмент кода имеет именно такую сложность:

procedure Slow; var

i, j, k ; Integer; begin

for 1 : = 1 to N do

for j : = 1 to N do

for k := 1 to N do

// Выполнение каких-либо действий.

end;

procedure Fast; var

i, j : Integer; begin

for i := 1 to N do

for j := 1 to N do

// Выполнение каких-либо действий.

end;

procedure RuilBoth; begin Fast;

Slow; end;

Сложность рекурсивных алгоритмов

Рекурсивные процедуры (recursive procedure) - это процедуры, которые вызы­вают сами себя. Их сложность определяется очень тонким способом. Сложность многих рекурсивных алгоритмов зависит именно от количества итераций рекур­сии. Рекурсивная процедура может казаться достаточно простой, но она может очень серьезно усложнять программу, многократно вызывая саму себя. /

Следующий фрагмент кода описывает процедуру, которая содержит только две операции. Тем не менее, если задается число N, то эта процедура выполняется N раз. Таким образом, вычислительная сложность данного алгоритма равна 0(N).

procedure CountDown(N ; Integer); begin

if (N<=0) then exit;

CountDown(N-l); end;

Многократная рекурсия

Рекурсивный алгоритм, вызывающий себя несколько раз, называется много­кратной рекурсией (multiple recursion). Процедуры множественной рекурсии слож­нее анализировать, чем однократные алгоритмы, кроме того, они могут сделать ал­горитм гораздо сложнее.

Следующая процедура аналогична процедуре Count Down, только она вызы­вает саму себя дважды.

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

Страницы раздела: 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.