Использование памяти в среднем случае - анализ алгоритмов

Question

Как указано в заголовке, некоторые из них сталкиваются с трудностями при анализе использования памяти в среднем слое памяти (быстроразъем). Моя цель - определить среднюю внутреннюю фрагментацию выделенного блока (используя быстродействующий распределитель памяти).

До сих пор я не получил никуда, так как я действительно не знаю, как анализировать средний случай. Мои первые мысли заключались в том, что у вас есть 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). Так как в худшем случае у нас есть только один «быстрый список», который обрабатывается, скажем, в первую очередь. Тогда самый худший возможный сценарий состоит в том, что у нас есть только один большой блок размером n байтов, доступный для выделения, а запрошенная память составляет всего 1 байт, тогда n-1 байт пропадает больше всего?

Я, возможно, не имел никакого смысла, но любая помощь в этом становится понятной. Спасибо

Answer 1

Пусть T (n) будет потрачено впустую при назначении размера n. Должно быть очень просто рассчитать T (n), правильно? Для размера блока b, T (n) = b - (n% b)?

Вторая часть более нюансирована. Это будет зависеть от распределения размера запроса на распределение. Вероятно, вы можете считать, что потери равномерны, и в этом случае ваши средние отходы будут b/2.

Вывод b/2: Вероятность потери отходов i равна 1/b для любого i (равномерное предположение). Ожидаемая потеря = sum_i Probability_i Wastage_i = 0/b + 1/b + .... + (b-1)/b = (b-1)/2, которая приблизительно равна b/2.