数据结构与算法的分析 —— 平均时间复杂度 vs 分摊时间复杂度

平均时间复杂度：假定各种输入实例的出现符合某种概率分布（如均匀独立随机分布）之后，进而估计出的加权时间复杂度均值。

分摊时间复杂度，纵观连续的足够多次操作，并将其间总体所需的运行时间分摊至各次操作。与平均时间复杂度的本质不同在于，这里强调，操作序列必须是的确能够真实发生的，其中各次操作之间存在前后连贯的时序关系。