Это доказательство, где у нас есть таблица, которая может содержать n элементов. Каждый раз, когда мы полностью заполняем эту таблицу, мы хотим перенести элементы в другую таблицу, в которой новая таблица имеет двойной размер по сравнению со старой.
Цель доказательства - доказать, что стоимость вставки элемента в таблице 3n или можно рассматривать как 3 доллара. (Доказательство относится к амортизированному анализу и использует метод учета.)
Обоснование цены в 3 доллара заключается в следующем:
- 1 доллар требуется для вставки элемента в Таблица.
- 1 доллар сохраняется для последующего использования, когда нам нужно будет перейти на новую таблицу.
- 1 доллар предоставляется другому элементу в таблице для оплаты его перевода при необходимости.
Если мы будем делать это каждый раз, когда элемент вставляется в таблицу, когда приходит время переноса, у каждого элемента будет 1 кредит на оплату вставки в новую таблицу.
Теперь мой вопрос не об этом деле. Мне интересно знать, какова будет стоимость, если мы вместо этого изменили расширение с удвоения размера на утроение. Таким образом, каждый раз, когда мы заполняем таблицу, новая будет иметь размер, в 3 раза превышающий предыдущую.
Подумав некоторое время, я пришла к выводу, что она будет (1 + 1/2) n со следующим обоснованием:
1 доллар тратится на вставку элемента.
1 доллар сохраняется для того, чтобы этот элемент переместился в новая таблица, когда требуется.
1/2 доллара, передается другому элементу в таблице, чтобы помочь перевести ее на новую таблицу. Поэтому у нас есть (1 + 1/2) долларов.
Интересно, верно ли то, что я нашел.