Это, кажется, покрыто упражнением 41 в разделе 2.5 тома 1 «Искусство компьютерного программирования» Кнута.Кнут рассматривает блоки размером 1, 2, .. 2 ^ k с общим хранилищем, выделенным из n - Цитата следует
По индукции по k мы можем доказать, что общий объем памяти, потребляемый такими разделенными блоками, никогда не превышает kn;после каждого запроса на разбиение блока размером 2 ^ (k + 1) мы используем не более n позиций в разделенных 2 ^ k блоках и не более n позиций в неразбитых.
(конец кавычки)Поэтому я думаю, что вы можете рассматривать это так, как если бы у вас был распределитель памяти для блоков размером до 2 ^ (k + 1), что давало гарантию использования не более n (k + 1) хранилищ при использовании не более n хранилищ для доставкиблоки размером 2 ^ (k + 1) и отложенные запросы на меньшие блоки к индуктивно распределенному распределителю, который может обслуживать эти запросы, используя не более nk хранилища.Если вы начинаете с пула (k + 1) n блоков, магическому распределителю никогда не нужно больше, чем хранилищу kn, поэтому распределитель для блоков размером 2 ^ (k + 1) всегда будет иметь по крайней мере n хранилищ нетронутых фрагментовблоки для обслуживания запросов размером 2 ^ (k + 1) от.