Примеры анализа сложности алгоритмов — Блог программиста

Примеры анализа сложности алгоритмов

09.12.2017алгоритмы

Содержание:

  1. Еще одна статья по анализу алгоритмов?
  2. Пример 1
  3. Пример 2
  4. Пример 3
  5. Пример 4
  6. Пример 5
  7. Заключение и дополнительная литература

Еще одна статья по анализу алгоритмов?

Давным давно я написал статью, в которой была параллельная реализация алгоритма быстрой сортировки [1]. По ней я получил обратную связь. Одни ребята написали мне, что быстрая сортировка будет работать медленнее, чем их реализация (мне скинули «слегка оптимизированный» алгоритм сортировки пузырьком). В качестве аргумента я получил такую фразу:

«он (алгоритм быстрой сортировки) очевидно медленнее (‘посмотри сколько там кода вообще?’). Чем больше кода — тем медленнее работает, ведь код процессор должен выполнить».

Позже я опубликовал еще две статьи, в одной из которых описал математический аппарат, необходимый для асимптотического анализа [2], а в другой — методы анализа рекурсивных алгоритмов [3] (для них стандартные методы не работают). Очень старался описать все понятно и доступно, был уверен, что любой гуманитарий теперь сможет разобраться в этой теме, но нашлись другие ребята, которые тоже не все поняли. Статью они прочитали, но им не понравилось, что анализ ведется при (ntoinfty). Цитирую:

обычный размер массива в программах в районе 50-100 элементов, а на нем (мы запустили и проверили) быстрая сортировка работает медленнее пузырьковой на X миллисекунд, поэтому весь этот анализ — математическое фуфло. Никогда n не будет равно бесконечности, объем памяти ограничен же.

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

Статья ориентирована на студентов первых курсов (и выпускников, которым не повезло с преподавателями). Вы не узнаете из нее ничего нового, если понимаете (можете доступно объяснить коллегам) почему у этого фрагмента трудоемкость (Theta(ncdotlog(n))):

for (int i = 0; i < n; ++i) {    for (int j = 1; j < n; j *= 2) {      ++k;    }  }

А у этого — (Theta(n^3)):

for (int i = 0; i < n; ++i) {    for (int j = 0; j < n-i; ++j) {      for (int k = i; k < j; ++k) {        ++k;      }    }  }

Основные математические сведения, которые понадобятся нам для понимания материала — формулы суммирования:

(sumlimits_{i=1}^{n} 1 = n, ~~ Theta(sumlimits_{i=1}^{n} 1) = Theta(n))

(sumlimits_{i=1}^{n} i = frac{(1+n)}{2}cdot n, ~~ Theta(sumlimits_{i=1}^{n} i) = Theta(n^2) )

Пример 1

  for (int i = 0; i < n; ++i) { // B    for (int j = 1; j < m; ++j) { // A      a[i][j]++; // С    }  }

Трудоемкость операции инкремента значения элемента массива не зависит от размерности задачи (в данном случае n и m), т.е. ее трудоемкость равна (Theta(1)). Во внутреннем цикле будет выполнено m операций, т.е. (T^{A}_m = Theta(sumlimits_{j=0}^{m} 1) = Theta(m)), а во внешнем — n операций:

$$T^{B}_{n,m} = Theta(sumlimits_{i=1}^{n} T^{A}_m) = Theta(ncdot m)$$

Тут все просто, при этом не случайно в одном цикле начальное значение счетчика равно нулю, а в другом единице (на их месте могли бы стоять другие числа) — на трудоемкость это не влияет. В отличии от Скиены [4], который предлагает своим читателям попробовать посчитать число операций (поэтому вложенный цикл у него содержит что-то типа k++), я предлагаю перейти к графической интерпретации, поэтому использую массивы.

Графическая интерпретация примера 1

Пример 2

  // пример 2.1  for (int i = 0; i < n-1; ++i) { // B    for (int j = 0; j < n-i; ++j) { // A      a[i][j]++;     }  }

Если в этом примере заменить a[i][j]++ на

if (a[j] > a[j+1])    swap(a[j], a[j+1])

Получится пузырьковая сортировка (дальше используются обозначения (mathcal{O}) вместо (Theta), т.к. после замены в лучшем случае будет выполнено (Omega(n)) операций обмена, подробнее это описано в [2]).

Зачем это тут и чем отличается от примера 1? — Во вложенном цикле теперь перебираются элементы не до n, а до n-i, при этом i не является константой, а зависит от n, ряд моих читателей уверены, что это изменит асимптотическую сложность алгоритма. На самом же деле:

$$T^{A}_{n, i} = mathcal{O}(sumlimits_{j=0}^{n-i} 1) = mathcal{O}(n-i) = mathcal{O}(n)$$

Последнее действие понятно не всем. Ну в самом деле, считаете вы трудоемкость и у вас получается (Theta(n^4 — n^4 + n)), человек, не знакомый с асимптотическим анализом скажет, что в результате получится (Theta(n)). Однако, нельзя забывать, что асимптотические обозначения задают класс функций, т.е. нет разницы между (Theta(n^4)) и (Theta(10cdot n^4)), поэтому вне зависимости от того, что вычитается, при верхней оценке трудоемкости берется самая быстро растущая функция. В данном случае это (Theta(n^4)).

Таким образом, трудоемкость приведенного алгоритма можно оценить как:

$$T^{B}_n = Theta(n^2)$$

Графическая интерпретация примера 2.1

По приведенной картинке видно, что обработано будет примерно (frac{(n-1)^2}{2}) элементов матрицы. Из этого примера можно сделать вывод о том, что «игры» с начальным и конечным значением счетчика цикла обычно на трудоемкость не влияют. В частности у такого алгоритма:

  // пример 2.2  for (int i = 0; i < n; ++i) { // B    for (int j = i; j < n-i; ++j) { // A      a[i][j]++;     }  }

Трудоемкость также оценивается (n^2), а выполнено будет примерно (n^2/4) операций:

Графическая интерпретация примера 2.2

Пример 3

Если в примере 1 на каждой итерации цикла увеличивать счетчик не на 1, а скажем, на 2 — оценка трудоемкости также не изменится (будет обработана половина элементов массива). Однако что будет если счетчик изменять в 2 раза?

  for (int i = 0; i < n; ++i) { // B    for (int j = 1; j < n; j *= 2) { // A      a[i][j]++;     }  }

Счетчик вложенного цикла будет принимать значения:

$$1, 2, 4, 8, 16, … 2^k$$

При этом (k = log_2(n))

Таким образом, (T^{A}_n = Theta(log(n))), следовательно (T^{B}_n = Theta(n cdot log(n)))

Иллюстрация… представьте себе массив у которого обработаны только столбцы, индексы которых рассчитываются по приведенной выше формуле. Очень важно представить себе насколько медленно растет функция логарифма — это поможет понять почему быстрая сортировка или сортировка слиянием (с оценкой (Theta(ncdotlog(n)))) более эффективны чем пузырьковая или сортировка вставками (имеющие оценку (Theta(n^2))). Графики в этом случае не очень наглядны, т.к. очень быстро расходятся в разные стороны, предлагаю посмотреть в таблицу:

n (n^2) (ncdotlog_2(n))
50 2500 282
150 22500 1084
250 62500 1991
650 522500 6074

Пример 4

Очень надеюсь, что все кто не понимал почему при асимптотическом анализе можно отбрасывать константы (даже очень большие) разберутся посмотрев в приведенную таблицу. Но, что если эти константы являются границами цикла, как в примере?:

  for (int i = 0; i < 100; ++i) { // B    for (int j = 1; j < n; ++j) { // A      ++count;    }  }

$$T^{B}_{n} = Theta(sumlimits_{i=0}^{100} T^{A}_n) = Theta(100cdot n) = Theta(n)$$

Часто в задачах ограничено n, но это не значит что всегда можно его игнорировать. Так например, Скиена [4] приводит случай из жизни, когда к нему обратились за эффективным алгоритмом, который должен выполнить некоторые расчеты с (0 lt i lt 1000 000 000). Очевидно, что будь в нашем примере такое большое значение — его нельзя было бы не учитывать (его надо было бы считать за n).

Пример 5

Хорошо, а что если во вложенном цикле будет (frac{n}{i}) итераций?

  for (int i = 0; i < n; ++i) { // B    for (int j = 0; j < n/i; ++j) { // A      matrx[i][i]++;    }  }

Представили себе матрицу, в i-то строке которой обрабатываются (frac{n}{i}) строк?

$$T^{A}_{n,i} = Theta(sumlimits_{i=0}^{n/i} 1) = Theta(n/i)$$

$$T^{B}_{n} = Theta(sumlimits_{i=0}^{n} T^{A}_{n}) = Theta(sumlimits_{i=0}^{n} frac{n}{i})) = Theta(ncdotsumlimits_{i=0}^{n} frac{1}{i}) = Theta(ncdotlog(n))$$

Примеры 5 и 4 на самом деле очень сильно отличаются. В примере 3 каждая итерация вложенного цикла выполняла одинаковое число итераций (их количество (log(n))), а в примере 5 для каждой следующей строки матрицы обрабатывалось меньше столбцов, чем для предыдущей. Тем не менее, асимптотические оценки обоих примеров совпадают.

Графическая интерпретация примеров 3 и 5

На рисунке показаны зависимости количества итераций внутреннего цикла от номера итерации внешнего цикла для примеров 4 (оранжевый) и 5 (синий) для (n = 100 000). Надеюсь эта картинка поможет понять почему асимптотические оценки совпадают. Синяя функция быстро убывает (может показаться, что оценка этой функции должна быть «лучше»), но для маленький значений i ее значения огромны (именно поэтому на графике начальное значение (i = 1000).

Заключение и Литература по алгоритмам

В этой небольшой заметке я старался наглядно показать что значит трудоемкость алгоритма. Лично мне кажется, что примеры (картинки) с матрицами лучше отражают трудоемкость, чем широко распространенные в сети визуализации алгоритмов сортировки, включая «радужные визуализации» и «визуализации танцами». Тем не менее, моя цель — привлечь внимание к математическому аппарату, который лежит в основе всего этого. Очень надеюсь что кто-нибудь заинтересуется и перейдет по рекомендованным ниже ссылкам.

  • Васильев В. С. Параллельные задачи (tasks) OpenMP [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1220. Дата обращения: 09.12.2017.
  • Васильев В. С. Анализ сложности алгоритмов. Примеры [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1660. Дата обращения: 09.12.2017.
  • Васильев В. С. Рекурсия в программировании. Анализ алгоритмов [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/813. Дата обращения: 09.12.2017.
  • Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
  • Аннотации на хорошую литературу по алгоритмам [Электронный ресурс] – режим доступа: https://pro-prof.com/books-algorithms. Дата обращения: 09.12.2017.

Метки:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *