正如标题所述，我在分析内存分配器 (quick-fit) 的平均内存使用情况时遇到了一些困难。我的目标是确定分配 block 的平均情况内部碎片(使用快速适配内存分配器)。
到目前为止我还没有真正取得任何进展，因为我真的不知道如何分析平均情况。我的第一个想法是，假设您有 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 字节？
我可能没有任何意义，但如果您能帮助我们更清楚地说明这一点，我们将不胜感激。 谢谢
最佳答案
令 T(n) 为进行 n 大小分配时浪费的空间。计算 T(n) 应该很简单吧？对于 b 的 block 大小，T(n) = b - (n%b) ?
第二部分更加微妙。这将取决于分配请求大小的分布。您可能会假设浪费是均匀的，在这种情况下，您的平均浪费将为 b/2。
b/2 的推导:对于任何 i，有浪费 i 的概率为 1/b(统一假设)。预期浪费 = sum_i Probability_i Wastage_i = 0/b + 1/b+....+ (b-1)/b = (b-1)/2 约等于 b/2。
关于algorithm - 平均情况内存使用 - 算法分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8934551/