Что такое амортизированный анализ алгоритмов? [закрыто]

Чем он отличается от асимптотического анализа? Когда вы его используете и почему?

Я прочитал несколько статей, которые, кажется, были написаны хорошо, например:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

но я до сих пор не полностью понял эти концепции.

Итак, может ли кто-нибудь упростить это для меня?

Амортизированный анализ не умножает наивно количество вызовов с худшим случаем для одного вызова.

Например, для динамического массива, размер которого при необходимости увеличивается вдвое, обычный асимптотический анализ только заключает, что добавление к нему элемента стоит O (n), потому что может потребоваться увеличение и копирование всех элементов в новый массив. Амортизированный анализ учитывает, что для роста необходимо добавить n / 2 элементов, не вызывая роста с момента предыдущего роста, поэтому добавление элемента действительно занимает всего O (1) (стоимость O (n) равна амортизировано более n / 2 акций).

Амортизированный анализ - это не то же самое, что «средняя производительность» - амортизированный анализ дает твердую гарантию того, что будет с производительностью, если вы сделаете так много действий.

На «что» есть много ответов, но «почему» нет.

Как уже говорили все, асимптотический анализ касается того, как производительность данной операции масштабируется до большого набора данных. Амортизированный анализ - это то, как масштабируется среднее значение производительности всех операций с большим набором данных. Амортизированный анализ никогда не дает худших оценок, чем асимптотический, а иногда дает гораздо лучшие.

Если вас интересует общее время выполнения более продолжительной работы, то, вероятно, вас волнуют лучшие границы амортизированного анализа. Вот почему языки сценариев (например) часто с радостью увеличивают массивы и хэш-таблицы по тем или иным причинам, даже если это дорогостоящая операция. (Выращивание может быть O(n)операцией, но амортизируется O(1)потому, что вы делаете это редко.)

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

Какой из них имеет значение в вашем случае, зависит от того, в чем именно заключается ваша проблема программирования.

Асимптотический анализ

Этот термин относится к анализу производительности алгоритма в предположении, что данные, с которыми работает алгоритм ( входные данные ), с точки зрения непрофессионала, «достаточно велики, чтобы их увеличение не повлияло на вывод». Хотя точный размер входа не требуется указывать (нам нужно только верхняя граница), набор данных , сам должен быть указан.

Обратите внимание, что до сих пор мы говорили только о методе анализа; мы не указали точно, какое количество мы анализируем (временная сложность? пространственная сложность?), и мы также не указали, какая метрика нас интересует (худший случай? лучший случай? средний?).

На практике термин асимптотический анализ обычно относится к верхней границе временной сложности алгоритма, т. Е. Производительности в наихудшем случае, измеренной общим временем выполнения, которое представлено обозначением big-Oh (например, может быть алгоритм сортировки O(nlogn)).

Амортизированный анализ

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

С точки зрения непрофессионала, амортизированный анализ выбирает произвольный размер для входных данных, а затем «проигрывает» алгоритм. Всякий раз, когда необходимо принять решение, зависящее от входных данных, выбирается худший путь ». После завершения работы алгоритма мы делим вычисленную сложность на размер входных данных, чтобы получить окончательный результат.

¹Примечание: Если быть точным, худший путь, который теоретически возможен . Если у вас есть вектор, размер которого динамически увеличивается вдвое каждый раз, когда его емкость исчерпывается, «худший случай» не означает, что он должен удваиваться при каждой вставке, потому что вставки обрабатываются как последовательность. Нам разрешено (и мы действительно должны) использовать известное состояние для математического исключения как можно большего количества «еще худших» случаев, даже если входные данные остаются неизвестными.

Самое главное отличие

Критическое различие между асимптотическим и амортизированным анализом состоит в том, что первый зависит от самих входных данных, а второй - от последовательности операций, которые алгоритм будет выполнять.

Следовательно:

• асимптотический анализ позволяет нам утверждать, что сложность алгоритма, когда ему дается лучший / худший / средний входные данные размером, приближающимся к N , ограничена некоторой функцией F (N) - где N - переменная
• Амортизированный анализ позволяет нам утверждать, что сложность алгоритма, когда ему на входе неизвестны характеристики, но известен размер N, не хуже, чем значение функции F (N), где N - известное значение

Ответ на этот вопрос кратко определяется первым предложением главы «Амортизированный анализ» книги - Введение в алгоритмы:

В амортизированном анализе время, необходимое для выполнения последовательности операций со структурой данных, усредняется по всем выполненным операциям.

Мы представляем сложность роста программы с помощью асимптотического анализа, который ограничивает рост программы функцией и определяет худший, лучший или средний случай этого.

Но это может вводить в заблуждение в тех случаях, когда есть только один случай, когда сложность программы достигает пика, но в целом программа не требует много вычислений.

Следовательно, имеет смысл усреднять стоимость по последовательности операций, даже если одна операция может быть дорогостоящей. Это амортизированный анализ!

Амортизированный анализ - это альтернатива асимптотическому методу, используемому для расчета сложности. Это помогает нам рассчитать более точную сложность с точки зрения практичности, чтобы сравнить и выбрать между двумя или более алгоритмами.

Лучшая справочная информация, которую я нашел до сих пор для понимания амортизированного анализа алгоритмов, - это книга Введение в алгоритмы , третье издание, глава 17: «Амортизированный анализ». Все это здесь, объяснено гораздо лучше, чем то, что можно найти в сообщении о переполнении стека. Вы найдете книгу в библиотеке любого приличного университета.

При регулярном асимптотическом анализе производительность отдельной операции рассматривается асимптотически в зависимости от размера задачи. Обозначение O () указывает на асимптотический анализ.

Амортизированный анализ (который также является асимптотическим анализом) смотрит на общую производительность нескольких операций над общей структурой данных .

Разница в том, что амортизированный анализ обычно доказывает, что общие вычисления, необходимые для M операций, имеют лучшую гарантию производительности, чем M раз наихудший случай для отдельной операции.

Например, отдельная операция над расширяемым деревом размера N может занять до O (N) времени. Однако последовательность из M операций над деревом размера N ограничена временем O (M (1 + log N) + N log N), что составляет примерно O (log N) на операцию. Однако обратите внимание, что амортизированный анализ намного строже, чем анализ «среднего случая»: он доказывает, что любая возможная последовательность операций удовлетворяет ее наихудшему асимптотическому случаю.

Амортизированный анализ имеет дело с общей стоимостью нескольких прогонов рутины и преимуществами, которые могут быть получены в результате этого. Например, поиск одного совпадения в несортированном массиве из n элементов может потребовать до n сравнений и, следовательно, имеет сложность o (n). Однако, если мы знаем, что в том же массиве будет выполняться поиск m элементов, повторение всей задачи будет иметь сложность O (m * n). Однако, если мы отсортируем массив заранее, стоимость будет O (n log (n)), а последовательные поиски потребуют только O (log (n)) для отсортированного массива. Таким образом, общая амортизированная стоимость m элементов при таком подходе равна O (n * log (n) + m * log (n)). Если m> = n, это приравнивается к O (n log (n)) путем предварительной сортировки по сравнению с O (n ^ 2) для отсутствия сортировки. Таким образом амортизированная стоимость дешевле.

Проще говоря, потратив немного больше на раннем этапе, мы сможем значительно сэкономить позже.