文件名称：分摊时间-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:06
数据结构 邓俊辉
O(1)分摊时间 以可扩充向量为例，可以考查对该结构的连续n次（查询、插入或删除等）操作，将所 有操作中用于内部数组扩容的时间累计起来，然后除以n。只要n足够大，这一平均时间就是 用于扩容处理的分摊计算时间。以下我们将看到，即便排除查询和删除操作而仅考查插入操 作，可扩充向量单次操作中用于扩容处理的分摊计算时间也不过O(1)。 假定数组的初始容量为常数N。既然是估计复杂度的上界，故不妨设向量的初始规模也 为N即将溢出。另外不难看出，除插入操作外，向量其余的接口操作既不会直接导致溢 出，也不会增加此后溢出的可能性，因此不妨考查最坏的情况，假设在此后需要连续地进行 n次insert()操作，n >> N。首先定义如下函数： size(n) = 连续插入n个元素后向量的规模 capacity(n) = 连续插入n个元素后数组的容量 T(n) = 为连续插入n个元素而花费于扩容的时间