dc.*_*dc. 5 theory arrays tree performance linked-list
这是一个分配问题,我在回答问题时遇到了问题.
"假设一个树每个节点最多可以有k个子节点.假设v是每个节点的平均子节点数.对于v的值,将子节点存储在一个节点中的效率更高(就使用的空间而言)链表与数组中的存储？为什么？"
我相信我能回答"为什么？" 或多或少用简单的英语 - 使用链表更有效率,因为而不是拥有一堆空节点(如果你的平均值低于最大值,数组中的空索引)占用内存你只需要分配空间当您实际填写值时,对于链接列表中的节点.
因此,如果在最大值为200时平均有6个子节点,则在创建树时,阵列将为每个节点的所有200个子节点创建空间,但链接列表将仅根据需要为节点分配空间.因此,使用链表,使用的空间大约是(？)平均值; 使用数组,间隔使用将是最大值.
...我不知道何时使用该阵列会更有效率.这是一个棘手的问题吗？我是否必须考虑到数组在创建时需要对节点总数进行限制的事实？
...我不知道何时使用该阵列会更有效率.这是一个棘手的问题吗？
这不是一个技巧问题.想想链表有的内存开销.如何实现链表(与数组相比)？
另外(虽然这超出了问题的范围!),空间消耗并不是实践中唯一的决定因素.缓存在现代CPU中起着重要作用,并且将各个子节点存储在数组而不是链表中可以极大地改善缓存局部性(从而提高树的性能).
对于许多常用语言,该阵列将需要分配存储k个存储器地址(数据).单链表将需要每个节点2个地址(数据和下一个).双链表将需要每个节点3个地址.
设n是特定节点A的实际子节点数:
值k允许您确定与简单地将地址存储在数组中相比,2 n或3 n个地址是平均增益还是损失.