Чем он отличается от асимптотического анализа? Когда вы его используете и почему?
Я прочитал несколько статей, которые, кажется, были написаны хорошо, например:
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), потому что вы делаете это редко.)
Если вы занимаетесь программированием в реальном времени (отдельные операции должны завершаться в предсказуемое время), то более точные оценки амортизированного анализа не имеют значения. Не имеет значения, была ли операция в среднем быстрой, если вы не успели закончить ее вовремя, чтобы вернуться и отрегулировать ленточную пилу до того, как она прорежет слишком далеко ...
Какой из них имеет значение в вашем случае, зависит от того, в чем именно заключается ваша проблема программирования.
Этот термин относится к анализу производительности алгоритма в предположении, что данные, с которыми работает алгоритм (вход), с точки зрения непрофессионала, «достаточно велики, чтобы их увеличение не повлияло на вывод». Хотя точный размер входных данных указывать не нужно (нам нужна только верхняя граница), сам набор данных должен быть указан.
Обратите внимание, что до сих пор мы говорили только о методе анализа; мы не указали точно, какое количество мы анализируем (временная сложность? пространственная сложность?), и мы также не указали, какая метрика нас интересует (худший случай? лучший случай ? средний?).
На практике термин асимптотический анализ обычно относится к временной сложности верхней границы алгоритма, т. Е. К производительности наихудшего случая, измеренной общим временем выполнения, которое представлено обозначением большого О (например, алгоритм сортировки может быть O(nlogn)).
Этот термин относится к анализу производительности алгоритма на основе определенной последовательности операций, нацеленной на наихудший сценарий, то есть амортизированный анализ подразумевает, что метрикой является производительность наихудшего случая (хотя он по-прежнему не сказать, какое количество измеряется). Чтобы выполнить этот анализ, нам нужно указать размер ввода, но нам не нужно делать никаких предположений относительно его формы.
С точки зрения непрофессионала, амортизированный анализ выбирает произвольный размер для входных данных, а затем «проигрывает» алгоритм. Всякий раз, когда необходимо принять решение, зависящее от входных данных, выбирается худший путь ». После завершения работы алгоритма мы делим вычисленную сложность на размер входных данных, чтобы получить окончательный результат.
¹Примечание: если быть точным, наихудший путь теоретически возможный. Если у вас есть вектор, размер которого динамически удваивается каждый раз, когда его емкость исчерпывается, "худший случай" не означает, что ему нужно будет удваиваться при каждой вставке, потому что вставки обрабатываются как последовательность . Нам разрешено (и мы действительно должны) использовать известное состояние, чтобы математически исключить как можно больше «даже худших» случаев, даже если входные данные остаются неизвестными.
Критическое различие между асимптотическим и амортизированным анализом состоит в том, что первый зависит от самих входных данных, а второй - от последовательности операций, которые алгоритм будет выполнять.
Следовательно:
O(1).
- person btilly; 04.09.2014
Ответ на этот вопрос кратко определяется первым предложением главы «Амортизированный анализ» книги - Введение в алгоритмы:
В амортизированном анализе время, необходимое для выполнения последовательности операций со структурой данных, усредняется по всем выполненным операциям.
Мы представляем сложность роста программы с помощью асимптотического анализа, который ограничивает рост программы функцией и определяет наихудший, лучший или средний случай этого.
Но это может ввести в заблуждение в тех случаях, когда есть только один случай, когда сложность программы достигает пика, но в целом программа не требует больших вычислений.
Следовательно, имеет смысл усреднять стоимость по последовательности операций, даже если одна операция может быть дорогостоящей. Это амортизированный анализ!
Амортизированный анализ - это альтернатива асимптотическому методу, используемому для расчета сложности. Это помогает нам вычислять более точную сложность с точки зрения практичности, чтобы сравнивать и выбирать между двумя или более алгоритмами.
Лучшая справочная информация, которую я нашел до сих пор для понимания амортизированного анализа алгоритмов, находится в книге Введение в алгоритмы, третье издание, глава 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) для отсутствия сортировки. Таким образом амортизированная стоимость дешевле.
Проще говоря, потратив немного больше на раннем этапе, мы сможем значительно сэкономить позже.
