Блог

Я не мог понять этот вопрос, может ли кто-нибудь, кто знает об этой проблеме, показать мне решение?

Священник Фрэнсис, ответственный за колокольный звон, создал устройство, которое автоматически звонит в колокола. Каждый точный час устройство звонит по крайней мере 1 из n звонков. В частности, i-й звонок звонит каждые 1 час. Например, предположим, что n = 4 и что отец Франциско включил свое устройство сразу после полуночи. Схема звонка колокола показана ниже. Каково амортизированное количество звонков, звонящих в час, в зависимости от n?

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

Применительно к этому случаю, без амортизации вы могли бы считать сложность наихудшим случаем за один час (могут прозвенеть все n звонков), умноженное на количество часов (вы не указали, поэтому я предполагаю, что это переменная, h). Таким образом, мы получили бы O (nh) всего звонков, выполняемых с O (n) звонками, выполняемыми в любой данный час. Однако все n звонков звонят так редко (в частности, только каждые n! часов), что, возможно, с амортизацией мы сможем добиться большего.

Затем мы стремимся получить амортизированное количество звонков, прозвеневших в час, как общее количество звонков, прозвеневших за все h часов, T (n, h), деленное на h. Чтобы получить эту общую сумму, обратите внимание, что Bell1 будет звонить h раз, Bell2 будет звонить h / 2 раза, Bell3 h / 3 раза и так далее. Затем T (n, h) определяется суммой:

T (n, h) в h раз больше гармонического ряда вплоть до n, поэтому мы можем представить его как hH (n), где H (n) обозначает n-й номер гармоники. Это означает амортизированную сложность за один час, поскольку общее количество прозвеневших звонков, деленное на количество часов, равно H (n).

Известно, что H (n) аппроксимируется ln (n), поскольку n стремится к бесконечности (по существу, потому, что H (n) является приблизительно интегралом от 1 / x dx = ln (n)), поэтому амортизированная сложность выражается в среднем количестве звонков в час, это O (ln (n)) = O (logn).