Анализ амортизированного времени в мин куче
У меня есть минимальная куча, которая содержит k чисел со счетчиком того, сколько раз мы получили это число от пользователя (например, мы могли бы иметь число 5 со счетчиком 0, чтобы не отображаться в пользовательском вводе). Функция вставки выполняется в O(logk), а функция FindMin работает следующим образом:
FindMin: взять корень кучи в O(1), если его счетчик не равен 0, вернуть это число. иначе DeleteMin в O(logk) и FindMin снова.
Теперь я знаю, что амортизированное время m вызовов insert и findmin равно O(logk), но я застрял в том, как это доказать. Это то, что я до сих пор:
Предположим, что M1 - это количество вызовов FindMin, а M2 - количество вызовов Insert. Мы знаем, что M1+M2=m, давайте также предположим, что K - это число узлов, на которых мы использовали DeleteMin в куче. Тогда мы знаем, что $\sum_{k=1}^M1 k <= M2$ и так:
T (m) = $ \ sum_ {k = 1} ^ M2 O(logk) $ + $\sum_{k=1}^M1 k*O(logk)$
и отсюда я не уверен, куда идти, мне кажется, что я получу T(m)=O(M2 * logk), который не является правильным ответом.
Любая помощь приветствуется!