文件名称：分摊时间-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2024-07-30 10:59:00
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
第2章 向量 §2.4 劢态空间管理 3355 2.4.4 分摊分析 时间代价 与常规数组实现相比，可扩充向量更加灵活：只要系统尚有可用空间，其规模将不再受限于 初始容量。不过，这并非没有代价每次扩容，元素的搬迁都需要花费额外的时间。 准确地，每一次由n到2n的扩容，都需要花费O(2n) = O(n)时间这也是最坏情况下， 单次插入操作所需的时间。表面看来，这一扩容策略似乎效率很低，但这不过是一种错觉。 请注意，按照此处的约定，每花费O(n)时间实施一次扩容，数组的容量都会加倍。这就意 味着，至少要再经过n次插入操作，才会因为可能溢出而再次扩容。也就是说，随着向量规模的 不断扩大，在执行插入操作之前需要进行扩容的概率，也将迅速降低。故就某种平均意义而言， 用于扩容的时间成本不至很高。以下不妨就此做一严格的分析。 分摊复杂度 这里，不妨考查对可扩充向量的足够多次连续操作，并将其间所消耗的时间，分摊至所有的 操作。如此分摊平均至单次操作的时间成本，称作分摊运行时间（amortized running time）。 请注意，这一指标与平均运行时间（average running time）有着本质的区别（习题[2-1]）。 后者是按照某种假定的概率分布，对各种情况下所需执行时间的加权平均，故亦称作期望运行时 间（expected running time）。而前者则要求，参与分摊的操作必须构成和来自一个真实可 行的操作序列，而且该序列还必须足够地长。 相对而言，分摊复杂度可以针对计算成本和效率，做出更为客观而准确的估计。比如在这里， 在任何一个可扩充向量的生命期内，在任何足够长的连续操作序列中，以任何固定间隔连续出现 上述最坏情况的概率均为0，故常规的平均复杂度根本不具任何参考意义。作为评定算法性能的 一种重要尺度，分摊分析（amortized analysis）的相关方法与技巧将在后续章节陆续介绍。 O(1)分摊时间 以可扩充向量为例，可以考查对该结构的连续n次（查询、插入或删除等）操作，将所有操 作中用于内部数组扩容的时间累计起来，然后除以n。只要n足够大，这一平均时间就是用于扩容 处理的分摊时间成本。以下我们将看到，即便排除查询和删除操作而仅考查插入操作，在可扩充 向量单次操作中，用于扩容处理的分摊时间成本也不过O(1)。 假定数组的初始容量为某一常数N。既然是估计复杂度的上界，故不妨设向量的初始规模也 为N即将溢出。另外不难看出，除插入操作外，向量其余的接口操作既不会直接导致溢出， 也不会增加此后溢出的可能性，因此不妨考查最坏的情况，假设在此后需要连续地进行n次 insert()操作，n >> N。首先定义如下函数： size(n) = 连续插入n个元素后向量的规模 capacity(n) = 连续插入n个元素后数组的容量 T(n) = 为连续插入n个元素而花费于扩容的时间 其中，向量规模从N开始随着操作的进程逐步递增，故有： size(n) = N + n 既然不致溢出，故装填因子绝不会超过100%。同时，这里的扩容采用了“懒惰”策略 只有在的确即将发生溢出时，才不得不将容量加倍因此装填因子也始终不低于50%。