Рассмотрим последовательность операций, в которой сложность операции номер i равна i*log(i), если i является степенью двойки, и 1 в противном случае. Оцените амортизационную стоимость одной операции методом потенциалов.

задан 5 Ноя '16 22:01

изменен 6 Ноя '16 3:55

А что понимается под "амортизационной стоимостью"?

(5 Ноя '16 23:46) falcao

Согласно определению из книги Кормена -"Построение и анализ", под амортизационной стоимостью понимается средняя стоимость затрат, приходящаяся на одну операцию, которая определяется соотношением T(n)/n, где T(n) - общее время выполнения последовательности всех n операций.

(5 Ноя '16 23:55) killedbymath
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,297
×1,193
×116
×16

задан
5 Ноя '16 22:01

показан
380 раз

обновлен
6 Ноя '16 3:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru