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

Question

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

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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