动态表

简单阐述一下动态表的基本思想,先建立一个表,当插入的元素大于表的大小时,建立一个新表(大小为旧表的两倍),并将旧表中的所有数据复制到新表中,然后插入新元素,最后摧毁掉旧表。如此反复,就能获得一个动态的哈希表。

平摊分析

所谓平摊分析,就是如果一个算法的曲线变换比较的激烈,比如 动态表,在插入的项正好大于表的大小时,在那一次的插入操作将会建立一个新表,并将原表的内的数据复制到新表这种,这将会造成O(n)的插入时间。但是在普通的插入状态下,没有复制操作,时间是O(1)的。所以并不能依赖最差情况O(n)的插入时间就断定插入n个元素时的复杂度为O(n^2).

这是不公平同时也是错误的,所以平摊分析就是将一个不那么平均的算法用平均的眼光看待,将其平均化,从而更加准确的分析与判断这个算法。

本章节,我们将介绍三种平摊算法 分别是 聚集分析 记账方法 势能方法

聚集分析

聚集分析本身就是将每个独立的操作加起来,最后 / n 就是单个的时间成本,不过这种方法可能会具有一些局限性,因为有时间加的操作可能会存在一些困难。

记账方法

记账方法将消耗的成本变得更加形象化。

首先,你是一个财务管理员,对于一次操作,我们会赋予他费用(就类似与每次给你三块钱,你自己去花),这些费用将用于支付具体操作,我们将这些费用称之为 摊还代价。如果某个操作用不完这些摊还代价(零花钱太多了用不完),将会存到银行之中,称之为 信用。所有的操作除了能够使用这次派发的 摊还代价之外,也能够使用信用支付。但是,每次操作使用的费用必须小于你的存款和这次摊还代价的总和。也就是说,你必须准备足够的钱来支付你的操作。

公式实在不好画,就不画了

总的来说,如果用Ci 来代表 第i个操作的真实代价(这次真正花了多少钱),用ci^来代表第i个操作的摊还代价(每次给的零花钱 每次给的钱都是一样的),那么如果有一个操作序列,那么 摊还代价的总和 > 真实代价的总和 必须!

所以我们的目的就是找到那个摊还代价,也就是每次发给他的零花钱,从而让整个公式成立,不让这个序列操作破产。当然是越不浪费越好

exp 动态表用记账

每次给3块钱自己花 插入一次花一块 复制一次花一块 多的存起来 case1 空间足够 用一块就够了 多的两块存银行 case2 空间不够了 全部复制+插入

大致上就是这样,最好还是画个表,尝试找出其中的一些规律,这个结果就是得出 3块钱刚好够花,所以我们认为单次插入的平摊成本大概就是3

势能方法

与记账方法类似,势能方法利用了物理中的势能概念来描述整个模型。

基本框架

  • 引入概念 数据结构 D_0
  • 操作i 将D(i - 1) 转化为 Di(把数据结构上的操作看成映射)
  • 操作代价为C_i
  • 建立一个势能函数 Φ() 他会把数据结构中的一个值映射成一个实数

核心公式 如果假设操作i的平摊代价为c^i 那么

c^i = ci + Φ(Di) - Φ(D(i - 1)) 其中 Φ(Di) - Φ(D(i - 1)) 意为势能变化 ΔΦi

势能变化

当势能变化>0的时候 c^i < c_i 也就是说当前的实际操作付出的代价超出了平摊代价,这意味着我们需要从势能库中拿一些出来补贴。

当势能变化<0的时候 正好相反 实际操作的代价小于平摊代价,可能存放一些势能。

至于如何去运用势能方法,就是依赖猜测那个势能函数。

总结

平摊分析的不同方法可能擅长分析不同的算法。并且他在分析相同算法的时候,的出来的结果可能也是不一致的。