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

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

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

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

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

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

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

Статья ориентирована на студентов первых курсов (и выпускников, которым не повезло с преподавателями). Вы не узнаете из нее ничего нового, если понимаете (можете доступно объяснить коллегам) почему у этого фрагмента трудоемкость \(\Theta(n\cdot\log(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;
    }
  }
}

Основные математические сведения, которые понадобятся нам для понимания материала — формулы суммирования:
\(\sum\limits_{i=1}^{n} 1 = n, ~~ \Theta(\sum\limits_{i=1}^{n} 1) = \Theta(n)\)
\(\sum\limits_{i=1}^{n} i = \frac{(1+n)}{2}\cdot n, ~~ \Theta(\sum\limits_{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(\sum\limits_{j=0}^{m} 1) = \Theta(m)\), а во внешнем — n операций:
$$T^{B}_{n,m} = \Theta(\sum\limits_{i=1}^{n} T^{A}_m) = \Theta(n\cdot m)$$

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

algorithm_example_1
Графическая интерпретация примера 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}(\sum\limits_{j=0}^{n-i} 1) = \mathcal{O}(n-i) = \mathcal{O}(n)$$

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

Таким образом, трудоемкость приведенного алгоритма можно оценить как:
$$T^{B}_n = \Theta(n^2)$$

algorithm_example_2_1
Графическая интерпретация примера 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\) операций:

algorithm_example_2_2
Графическая интерпретация примера 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(n\cdot\log(n))\)) более эффективны чем пузырьковая или сортировка вставками (имеющие оценку \(\Theta(n^2)\)). Графики в этом случае не очень наглядны, т.к. очень быстро расходятся в разные стороны, предлагаю посмотреть в таблицу:

n \(n^2\) \(n\cdot\log_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(\sum\limits_{i=0}^{100} T^{A}_n) = \Theta(100\cdot 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(\sum\limits_{i=0}^{n/i} 1) = \Theta(n/i)$$
$$T^{B}_{n} = \Theta(\sum\limits_{i=0}^{n} T^{A}_{n}) = \Theta(\sum\limits_{i=0}^{n} \frac{n}{i})) = \Theta(n\cdot\sum\limits_{i=0}^{n} \frac{1}{i}) = \Theta(n\cdot\log(n))$$

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

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

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

Заключение

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

Литература по алгоритмам

  • 57
    Поделились

Комментарии 2

  • Здравствуйте, Владимир! Спасибо за статью, очень доступно и наглядно. Понравились графики и практическая направленность.
    Однако остался вопрос по поводу примеров 4 и 5. Вы подчеркнули, что асимптотические оценки совпадают, хотя формулы в примерах приведены разные O(n) и O(n*log(n)). Правильно ли я понял, что в зависимости от соотношения константы и n, константу можно либо опустить, либо записать как log(n)?

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

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