DAA - Методология анализа
Для измерения потребления ресурсов алгоритма используются различные стратегии, как описано в этой главе.
Асимптотический анализ
Асимптотика функции f(n) относится к росту f(n) в качестве n становится большим.
Обычно мы игнорируем небольшие значения n, поскольку нас обычно интересует оценка того, насколько медленной будет программа при больших входных данных.
Хорошее практическое правило состоит в том, что чем медленнее скорость асимптотического роста, тем лучше алгоритм. Хотя это не всегда так.
Например, линейный алгоритм $ f (n) = d * n + k $ всегда асимптотически лучше, чем квадратичный, $ f (n) = cn ^ 2 + q $.
Решение рекуррентных уравнений
Повторение - это уравнение или неравенство, которое описывает функцию с точки зрения ее значения на меньших входах. Рецидивы обычно используются в парадигме «разделяй и властвуй».
Рассмотрим T(n) быть временем работы над проблемой размера n.
Если размер проблемы достаточно мал, скажите n < c где c - константа, прямое решение требует постоянного времени, которое записывается как θ(1). Если разделение задачи дает ряд подзадач размером $ \ frac {n} {b} $.
Для решения проблемы необходимо время. a.T(n/b). Если учесть, что время, необходимое для разделения, составляетD(n) а время, необходимое для объединения результатов подзадач, равно C(n), рекуррентное отношение может быть представлено как -
$$ T (n) = \ begin {case} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) и в противном случае \ end { case} $$
Рекуррентное отношение может быть решено с использованием следующих методов -
Substitution Method - В этом методе мы угадываем оценку и с помощью математической индукции доказываем, что наше предположение было правильным.
Recursion Tree Method - В этом методе формируется дерево повторения, где каждый узел представляет стоимость.
Master’s Theorem - Это еще один важный метод определения сложности рекуррентного отношения.
Амортизированный анализ
Амортизированный анализ обычно используется для определенных алгоритмов, в которых выполняется последовательность аналогичных операций.
Амортизированный анализ позволяет ограничить фактическую стоимость всей последовательности вместо того, чтобы отдельно определять стоимость последовательности операций.
Амортизированный анализ отличается от анализа среднего случая; вероятность не участвует в амортизированном анализе. Амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.
Это не просто инструмент для анализа, это способ размышления о дизайне, поскольку проектирование и анализ тесно связаны.
Агрегатный метод
Агрегатный метод дает глобальное представление о проблеме. В этом методе, еслиn операции требуют наихудшего времени T(n)в итоге. Тогда амортизированная стоимость каждой операции равнаT(n)/n. Хотя разные операции могут занимать разное время, в этом методе не учитывается разная стоимость.
Метод учета
В этом методе разные сборы назначаются разным операциям в соответствии с их фактической стоимостью. Если амортизированная стоимость операции превышает ее фактическую стоимость, разница присваивается объекту в качестве кредита. Этот кредит помогает оплачивать последующие операции, амортизированная стоимость которых меньше фактической.
Если фактическая стоимость и амортизированная стоимость ith операции $ c_ {i} $ и $ \ hat {c_ {l}} $, тогда
$$ \ Displaystyle \ сумма \ пределы_ {я = 1} ^ п \ шляпа {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$
Возможный метод
Этот метод представляет предоплаченную работу как потенциальную энергию, а не рассматривает предоплаченную работу как кредит. Эту энергию можно высвободить для оплаты будущих операций.
Если мы выполним n операции, начинающиеся с исходной структуры данных D0. Рассмотрим,ci как фактическая стоимость и Di как структура данных ithоперация. Потенциальная функция Ф отображается в действительное число Ф (Di) связанный потенциал Di. Амортизированная стоимость $ \ hat {c_ {l}} $ может быть определена как
$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$
Следовательно, общая амортизированная стоимость составляет
$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i}) ) - \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $
Динамический стол
Если выделенного места для таблицы недостаточно, мы должны скопировать таблицу в таблицу большего размера. Точно так же, если из таблицы стирается большое количество элементов, рекомендуется перераспределить таблицу с меньшим размером.
Используя амортизированный анализ, мы можем показать, что амортизированная стоимость вставки и удаления является постоянной, а неиспользуемое пространство в динамической таблице никогда не превышает постоянной доли от общего пространства.
В следующей главе этого руководства мы кратко обсудим асимптотические обозначения.