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

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

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

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

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

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

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

Спасибо!


analysis algorithm
person venkysmarty    schedule 07.09.2011    source источник
comment
проверьте это, второй комментарий, очень-очень хорошо! гарантия производительности в худшем случае">programmers.stackexchange.com/questions/161404/   -  person sorry_I_wont    schedule 23.07.2015
comment
@sorry_I_wont Похоже, комментарий был удален, так как я его не вижу.   -  person Franck Dernoncourt    schedule 26.11.2016

Ответы (3)


arrow_upward
13
arrow_downward

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

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

person Patrick87    schedule 07.09.2011
comment
Вы хорошо говорите о среднем случае, но вопрос был бы лучше, если бы в нем также было четко указано, что делает амортизированный случай. - person Mooing Duck; 05.11.2020

arrow_upward
54
arrow_downward

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

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

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

person RossFabricant    schedule 07.09.2011

arrow_upward
4
arrow_downward

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

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

person Simone    schedule 07.09.2011
comment
Как вычислить минимум в несортированном массиве только с n/2 сравнениями? Я думаю, вам нужно ровно n-1. И не только в среднем, а всегда. - person Stefan Pochmann; 12.07.2017
comment
Я согласен с @StefanPochmann. Я просто хотел добавить, что я бы изменил пример с поиском элемента в массиве. В этом случае, предполагая, что ваш алгоритм движется слева направо, пока не найдет элемент, он останавливается, когда находит его, и вы можете поддержать анализ, который вы делали. - person Raudel Ravelo; 08.07.2018