• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[算法导论]#1 摊还分析

admin

11月 28, 2021

引言

一个哈希表多大合适?

数据量为(n​),如果哈希表无限大(>=(n​)),那么时间复杂度是(O(1)​)的,不过很显然,虽然节省了时间,但是浪费了空间.

实际上在我们不知道数据量的情况下,我们无法确定哈希表的大小,这时我们有个很美丽的数据结构->动态表

动态表的工作原理

  • 建立一个表,初始化大小为1.
  • 如果表的容量不够,那么就把大小扩大为原来的两倍,将原来表的内容复制一遍
  • 把原来表的内存释放,再执行插入
  • 容量会以1,2,4,8,16……(2的幂次)的增长

接下来我们来分析一下插入操作的复杂度:

  • 当表里存在(n)个元素,最坏复杂度是(O(n)​)
  • (n)个元素插入的最坏复杂度是(O(n^2)​)

这个复杂度分析肯定是错的,理由是并不是每一项都是最坏的(O(n)​)的复杂度

这时就要用到平摊分析了,我们先从最简单的聚集分析说起.

聚集分析

容易发现,(n)个元素的插入必然需要一个(n​),但是只有当2的幂次的时候才会复制一遍

复杂度应该是:

[n+sum_{j=0}^{lfloor lg(n-1)floor} 2^j
]

右边这个最后也不会超过(2n)

证明

[sum_{j=0}^{lfloor log_2(n-1)floor} 2^j<=2n
]

最后总复杂度为(3n),就是(O(n)),平均下来每个操作就是(O(1))

用平摊分析来分析一个操作序列,证明每个操作的平均代价很小,尽管有个别操作可能代价很大.值得注意的是这个平均并没有用到概率论.它是最坏情况下的平均操作.就像上面这个例子,平均下来每步操作是常数级别的.(frac{O(n)}{n}​)

综上所述:

  • 平摊分析可以用来证明在一系列操作中,通过对所有操作求平均之后,即使其中单一的操作具有较大的代价,平均代价还是很小的
  • 平摊分析与平均情况分析的不同之处在于它不牵涉到概率
  • 平摊分析保证在最坏情况下,每个操作具有平均性能。

上文采用的方法是聚集分析,在聚集分析中,如证明对所有的n,由n个操作所构成的序列的总时间在最坏情况下为(O(n))。因此,在最坏情况下,每个操作的平均代价(或称平摊分析)为(frac{O(n)}{n})请注意这个平摊代价对每个操作都是成立的,即使当序列中存在几种类型的操作时也是一样的

换句话说,就是对(n)条操作整体考虑其复杂度,而不是单独考虑一条指令的最坏复杂度,然后再平摊.

但是,并不是所有情况都能像上文一样轻易地求出平摊复杂度,要采用更精确的方法.

记账方法

算法导论上称为核算法

设想自己是一个财务会计,而你要做的就是给第(i)个操作“付钱”,设一个虚构的平摊代价,称之为(check C_i),而每个操作的实际代价为(C_i)

设每一步运算要花费1元.例如执行一次普通的插入操作要花费1元,由空间为2的表扩大为空间为4的表再复制需要2元.

如果还有剩余的钱,那就把钱存起来,用于支付以后的操作.

如果$ check C_i​$不足以支付给这些操作,那就从银行里取出钱来付款.

存款余额要求不能是负数,当然所有的平摊代价减去操作代价的余额必须是非负数.

也就是相当于

[sum_{i=1}^{n}C_ileq sum_{i=1}^{n}check C_i
]

以动态表为例:

  • 初始设置(check C_i=3​),其中1元用于插入,2元用于将表翻倍的预存费用.

  • 当表扩大两倍,就从存款里取出1美元来移动新项,还有1美元来移动旧项.

  • 当长度为8的时候:

    里面的数字就是余额,前四个余额为0,这时开始执行插入操作

    花费1元用于插入,余额为2元,插入四个之后:

  • 这时动态表需要扩大两倍,扩大两倍需要多少钱?没错,非常完美地,余额为8刚好可以支付复制操作,然后新插入的第九项也是花费1元进行插入,余额为2元.

通过这个计算,我只需要每个操作预设(F_i=3),就可以足够支付了.

这样就可以得到总复杂度是 (3n)

当然进行平摊分析并不只有一个可行方案,若将平摊代价设置为4也是可以的,但是设置为2就不行了.

对记账方法进行总结:

在平摊分析的记帐方法中,决定每一个操作的均摊成本,对不同的操作赋予不同的费用,某些操作的费用比它们的实际代价或多或少。我们对一个操作的收费的数量称为平摊代价(check C_i​)。当一个操作的平摊代价超过了它的实际代价$ C_i ​$时,两者的差值就被当作存款,并赋予数据结构中的一些特定对象,可以用来补偿那些平摊代价低于其实际代价的操作。这种方法与聚集分析不同的是,对后者,所有操作都具有相同的平摊代价,对前者,操作的平摊代价被分解为实际代价余额。数据结构中存储的总存款等于总的平摊代价和总的实际代价之差。注意:总存款不能是负的。在开始阶段的存款,是为了在后面的操作序列中再支付。

势能法

好的势能方法,就像初恋一样无法忘怀.

我们由数据结构(D_0)开始讲起

  • 操作(i)(D_{i-1})转化为(D_i),操作(i)的操作代价还是$ C_i $

  • 定义势能函数(phi),将数据结构映射为实数

  • 这样初始的势能是(phi (D_0)=0) ,对于所有(i)都有$phi (D_0) geq 0 $

  • 平摊代价(check C_i=C_i+phi(D_i)-phi(D_{i-1}))

  • (Delta phi_i=phi(D_i)-phi(D_{i-1})​)是势能的改变量

势能法与记账法不同的是后者考虑的是平摊代价,前者考虑的是银行存款,也就是势能函数.

其中:

  • 如果(Delta phi_i geq 0) ,第(i)次操作存储了后面数据结构所需的代价
  • 如果(Delta phi _i leq0), 第(i)次操作消耗了之前数据结果存储的代价

平摊代价正确性证明:

[sum _{i=1}^{n}check C_i = sum_{i=1}^{n}(C_i+phi(D_i)-phi(D_{i-1}))
]

[=sum_{i=1}^{n}C_i+phi(D_n)-phi(D_0)    phi(D_0)=0   phi(D_n) geq 0
]

[geq sum_{i=1}^{n}C_i
]

动态表的势能法分析:

  • 定义势能函数(phi(D_i)=2i-2^{lceil logi ceil})

  • 可得(phi(D_0)=2^{log0}=0)

  • 因为(lceil lgi ceil​)向上取整,所以最大取到$ lgi +1​$,所以(2^{lceil lgi ceil}​)最大取到(2i​)(phi(D_i)ge0​)

  • 由$ check C_i=C_i+phi(D_i)-phi(D_{i-1})$

  • 实际代价(C_i)由上文可知分两种情况,一般情况下是(1),而当(i-1)(2)的幂时为(i)

    [phi(D_i)-phi(D_{i-1})=(2i-2^{lceil lgi ceil})-(2(i-1)-2^{lceil lg(i-1)ceil})
    ]

    [=2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
    ]

  • 分情况分析:当(i-1)(2)的幂次时:

    [check C_i=i+2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
    ]

    [= i+2-2(i-1)+i-1
    =3
    ]

  • 其他情况:

    [check C_i=1+2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
    ]

    [=1+2=3
    ]

总结

  • 平摊分析为数据结构的性能提供了一个简洁的抽象概念。
  • 在不关注实时表现,只关注聚集行为时,平摊分析是一种很好的描述方式。
  • 在有些情况中,不同的操作会有不同的平摊代价,它们的和仍然是实际代价的上限。
  • 三种方法都是可用的,但都有各自的适用情况使得它们是简单准确的,不同的方法可能得到不同的上限结果。

发表评论

您的电子邮箱地址不会被公开。