Род Стивенс

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

При вычислении значений «большого О» можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим циклом 3 * N2 рассматривается как 0(N2). Таким образом, зависимость отношения O(N) от изменения размера задачи более очевидна. Если увеличить N в 2 раза, эта двойка возводится в квадрат (N2) и время выполнения алгоритма увеличивается в 4 раза.

Игнорирование постоянных множителей также облегчает подсчет шагов вы­полнения алгоритма. В приведенном ранее примере внутренний цикл выполняет­ся N2 раз. Сколько шагов делает каждый внутренний цикл? Чтобы ответить на этот вопрос, вы можете вычислить количество условных операторов if, потому что только этот оператор выполняется в цикле каждый раз. Можно сосчитать общее количество инструкций внутри условного оператора if. Кроме того, внутри внеш­него цикла есть инструкции, не входящие во внутренний цикл, такие как команда PrintValue. Нужно ли считать и их?

С помощью различных методов подсчета можно определить, какую сложность имеет алгоритм N2,3 * N2, или 3 * N2 + N. Оценка сложности алгоритма по порядку величины даст одно и то же значение 0(№), поэтому неважно, сколько точно ша­гов имеет алгоритм.

Определение сложности

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

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

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

Если при выполнении циклов процедуры Fast всякий раз вызывается проце­дура Slow, то сложности процедур перемножаются. Общая сложность равна про­изведению обеих сложностей. В данном случае сложность алгоритма составляет 0(N2) * 0(N3) ИЛИ 0(№*№) = 0(№). Приведем соответствующий фрагмент кода:

procedure Slow; var

i, j, k : Integer; begin

for i := 1 to N do

for j := 1 to N do for k := 1 to N do 1 // Выполнение каких-либо действий.

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

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