Как видно из заголовка, у меня возникли некоторые трудности с анализом использования памяти в среднем регистре для выделения памяти ( quick-fit ). Моя цель - определить внутреннюю фрагментацию выделенного блока в среднем случае (с использованием быстродействующего распределителя памяти).
Пока я нигде не получил, так как не знаю, как анализировать средний случай. Сначала я подумал, что у вас есть T (n) , то есть память тратится впустую при выделении блока памяти размером n (внутренняя фрагментация). Кроме того, предположим, что вероятность выделения блока памяти размером n равна P (n), тогда средняя трата памяти случая должна в основном быть суммой T (n1) P (n1) + ( Tn2) P (n2) + .... + T (nk) P (nk)
Проблема в том, что я не знаю T (n) и P (n) .. или это вообще возможно без каких-либо предположений?
В худшем случае я просто думаю, что это O (n-1) = O (n). Поскольку в худшем случае у нас есть только один «быстрый список», который обрабатывается, скажем, first-fit . Тогда худший возможный сценарий состоит в том, что у нас есть только один большой блок размером n байтов, доступный для выделения, и запрошенная память занимает всего 1 байт, тогда n-1 байт теряется максимум?
Я не могу иметь никакого смысла, но любая помощь в разъяснении этого важна.
Спасибо