Комментарии 2
Что мы находим методом банкира, например? Т.е. каков физический смысл получаемой оценки?
Наихудшее время работы алгоритма будет O(N^2). Чему соответствует линейная оценка? Среднее время по случайным запускам с равномерно распределенными параметрами? Или чему-то другому?
Наихудшее время работы алгоритма будет O(N^2). Чему соответствует линейная оценка? Среднее время по случайным запускам с равномерно распределенными параметрами? Или чему-то другому?
У нас есть последовательность операций. Время выполнение каждой ведет себя как-то непонятно: где-то быстро, где-то медленно. Хочется посчитать суммарное время работы.
Амортизационная стоимость, как, например, в методе банкира — это такая усредненная по всем выполненным операциям верхняя оценка. Никакой случайности здесь нет. Среднее берем по выполненным операциям.
Амортизационная стоимость, как, например, в методе банкира — это такая усредненная по всем выполненным операциям верхняя оценка. Никакой случайности здесь нет. Среднее берем по выполненным операциям.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Амортизационный анализ