空间开销分析知识点


本节概述 本节知识点 本节总结

二、空间开销分析

1、结构性开销和存储密度：
    结构性开销γ是指为了实现数据结构而花费的辅助空间比例。这些辅助空间不是用来存储数据记录，而是为了保存数据结构的逻辑特性或为了方便运算。

    存储密度α (≤1)表示数据结构存储的效率。
显然α = 1 - γ。如果所有的存储空间都分配给了数据，则这个存储结构叫紧凑结构，否则叫非紧凑结构，紧凑结构的存储密度为1，非紧凑结构的存储密度小于1。显然二叉链表的存储是非紧凑结构。存储密度越大，则存储空间的利用效率越高。

2、根据满二叉树定理，一半的指针是空的。如果只有叶结点存储数据，分支结点为内部结构结点（如Huffman树），则开销取决于二叉树是否满（越满存储效率越高）。对于简单的每个结点存两个指针、一个数据域，空间(2p + d)n，结构性开销：2pn。如果p = d，则2p/(2p + d) = 2/3。去掉满二叉树叶结点中的指针


则结构性开销为1/2 （假设p = d）。如果只在叶结点存数据，则结构性开销为2pn/(2pn + d(n+1))= 2/3 （假设p = d）。注意区分叶结点和分支结点又需要额外的算法时间。