Чтобы измерить потребление ресурсов алгоритмом, используются разные стратегии, как описано в этой главе.
Асимптотический анализ
Асимптотическое поведение функции f (n) относится к росту f (n), когда n становится большим.
Обычно мы игнорируем небольшие значения n , так как мы обычно заинтересованы в оценке того, насколько медленной будет программа при больших входах.
Хорошее эмпирическое правило заключается в том, что чем ниже скорость асимптотического роста, тем лучше алгоритм. Хотя это не всегда так.
Например, линейный алгоритм f(n)=d∗n+k всегда асимптотически лучше квадратичного, f(n)=cn2+q.
Решение рекуррентных уравнений
Повторение — это уравнение или неравенство, которое описывает функцию в терминах ее значения на меньших входах. Рецидивы обычно используются в парадигме «разделяй и властвуй».
Рассмотрим T (n) как время выполнения задачи размера n .
Если размер задачи достаточно мал, скажем, n <c, где c — константа, прямое решение занимает постоянное время, которое записывается как θ (1) . Если разделение задачи приводит к ряду подзадач с размером fracnb.
Для решения проблемы требуется время aT (n / b) . Если мы считаем, что время, необходимое для деления, равно D (n), а время, необходимое для объединения результатов подзадач, — C (n) , рекуррентное соотношение можно представить в виде —
Т (п) = \ {начинаются случаи} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) и в противном случае \ end { случаи}
Рекуррентное отношение может быть решено с использованием следующих методов:
-
Метод замещения — В этом методе мы угадываем границу и, используя математическую индукцию, доказываем, что наше предположение было верным.
-
Метод дерева рекурсии — В этом методе формируется дерево рекурсии, где каждый узел представляет стоимость.
-
Теорема магистрата — это еще один важный метод, позволяющий найти сложность рекуррентного отношения.
Метод замещения — В этом методе мы угадываем границу и, используя математическую индукцию, доказываем, что наше предположение было верным.
Метод дерева рекурсии — В этом методе формируется дерево рекурсии, где каждый узел представляет стоимость.
Теорема магистрата — это еще один важный метод, позволяющий найти сложность рекуррентного отношения.
Амортизированный анализ
Амортизированный анализ обычно используется для определенных алгоритмов, в которых выполняется последовательность похожих операций.
-
Амортизированный анализ обеспечивает оценку фактической стоимости всей последовательности, а не оценку стоимости последовательности операций отдельно.
-
Амортизированный анализ отличается от анализа среднего случая; Вероятность не участвует в амортизированном анализе. Амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.
Амортизированный анализ обеспечивает оценку фактической стоимости всей последовательности, а не оценку стоимости последовательности операций отдельно.
Амортизированный анализ отличается от анализа среднего случая; Вероятность не участвует в амортизированном анализе. Амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.
Это не просто инструмент для анализа, это способ мышления о дизайне, поскольку проектирование и анализ тесно связаны.
Совокупный метод
Агрегатный метод дает глобальное представление о проблеме. В этом методе, если n операций занимает общее время времени наихудшего случая T (n) . Тогда амортизированная стоимость каждой операции равна T (n) / n . Хотя разные операции могут занимать разное время, в этом методе игнорируются различные затраты.
Метод учета
В этом методе разные операции назначаются разным операциям в соответствии с их фактической стоимостью. Если амортизированная стоимость операции превышает ее фактическую стоимость, разница присваивается объекту как кредит. Этот кредит помогает оплачивать последующие операции, для которых амортизированная стоимость меньше реальной стоимости.
Если фактическая стоимость и амортизированная стоимость i- й операции составляют ci и hatcl, то
displaystyle sum limitni=1 hatcl geqslant displaystyle sum limitni=1ci
Потенциальный метод
Этот метод представляет предоплаченную работу как потенциальную энергию, а не рассматривает предоплаченную работу в качестве кредита. Эта энергия может быть выпущена для оплаты будущих операций.
Если мы выполним n операций, начиная с исходной структуры данных D 0 . Рассмотрим, c i — фактическую стоимость, а D i — структуру данных i- й операции. Потенциальная функция Ф отображается в действительное число Ф ( D i ), связанный потенциал D i . Амортизированная стоимость hatcl может быть определена как
hatcl=ci+ Phi(Di)− Phi(Di−1)
Следовательно, общая амортизированная стоимость
$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limit_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i}) ) — \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) — \ Phi (D_ {0}) $ $
Динамическая таблица
Если выделенного пространства для таблицы недостаточно, мы должны скопировать таблицу в таблицу большего размера. Аналогично, если из таблицы удаляется большое количество элементов, рекомендуется перераспределить таблицу меньшего размера.
Используя амортизированный анализ, мы можем показать, что амортизированная стоимость вставки и удаления постоянна, а неиспользуемое пространство в динамической таблице никогда не превышает постоянной доли общего пространства.
В следующей главе этого руководства мы кратко обсудим асимптотические обозначения.