Разница между средним случаем и амортизированным анализом

Question

Я читаю статью об амортизированном анализе алгоритмов. Ниже приведен фрагмент текста.

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

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

Мои вопросы по поводу приведенного выше фрагмента текста:

1. В первом абзаце, как анализ среднего случая "опирается на вероятностные предположения о структурах данных и операциях?". Я знаю, что анализ среднего случая зависит от вероятности ввода, но что означает приведенное выше утверждение?

2. Что автор подразумевает во втором абзаце, что средний регистр недействителен, даже если входное распределение корректно?

Спасибо!

Answer 1

1. Чтобы получить сложность времени в среднем случае, вам нужно сделать предположения о том, что такое "средний случай". Если входные данные являются строками, что такое "средняя строка"? Имеет ли значение только длина? Если да, то какую среднюю длину я получу? Если нет, каков средний символ (ы) в этих строках? Становится трудно ответить на эти вопросы окончательно, если строки, например, фамилии. Какая средняя фамилия?

2. В наиболее интересных статистических выборках максимальное значение больше среднего. Это означает, что ваш анализ среднего случая иногда будет недооценивать время / ресурсы, необходимые для определенных входных данных (которые являются проблематичными). Если подумать, для симметричного PDF анализ среднего случая должен недооценивать столько, сколько он переоценивает. Анализ наихудших случаев, OTOH, рассматривает только самые проблемные случаи и, таким образом, может быть переоценен.

Answer 2

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

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

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

Answer 3

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

2. Во втором абзаце автор говорит, что при анализе среднего случая мы можем быть очень неудачливы и иметь измеренный средний случай больше, чем в терротическом случае; напоминая предыдущий пример, если нам не повезло с m различными массивами размера n, а минимум - каждый раз в последней позиции, то мы измерим n средний случай, а не n/2, Это не может произойти, когда доказана амортизация.