Python - Амортизированный анализ
Амортизированный анализ включает оценку времени выполнения последовательности операций в программе без учета диапазона распределения данных во входных значениях. Простой пример: найти значение в отсортированном списке быстрее, чем в несортированном. Если список уже отсортирован, не имеет значения, насколько распределены данные. Но, конечно, длина списка имеет значение, поскольку она определяет количество шагов, которые алгоритм должен пройти, чтобы получить окончательный результат.
Итак, мы видим, что если начальная стоимость одного шага получения отсортированного списка высока, то стоимость последующих шагов поиска элемента становится значительно ниже. Таким образом, амортизированный анализ помогает нам определить время выполнения последовательности операций в наихудшем случае. Есть три подхода к амортизированному анализу.
Accounting Method- Сюда входит назначение стоимости каждой выполненной операции. Если фактическая операция завершается быстрее, чем назначенное время, тогда в анализе накапливается некоторый положительный кредит. В обратном случае это будет отрицательный кредит. Чтобы отслеживать эти накопленные кредиты, мы используем структуру данных в виде стека или дерева. Операции, которые выполняются досрочно (например, сортировка списка), имеют высокую амортизированную стоимость, но операции, выполняемые с опозданием, имеют более низкую амортизированную стоимость по мере использования накопленного кредита. Таким образом, амортизированная стоимость - это верхняя граница фактической стоимости.
Potential Method- В этом методе сохраненный кредит используется для будущих операций как математическая функция от состояния структуры данных. Оценка математической функции и амортизированной стоимости должны быть равны. Таким образом, когда фактическая стоимость превышает амортизированную стоимость, потенциал уменьшается, и она используется для будущих дорогостоящих операций.
Aggregate analysis - В этом методе мы оцениваем верхнюю границу общей стоимости n шагов. Амортизированная стоимость представляет собой простое деление общей стоимости на количество шагов (n).