线段树合并时间复杂度的势能分析证明

· · 个人记录

关于线段树合并复杂度为O(nlogn)的势能分析法证明:

  1. 设势能函数φi,表示第i次操作后,线段树森林的节点数与每个节点(叶节点除外)左右儿子中空儿子的个数之和,(φ0=0,即一开始无节点)(此处也并非严格的个数,可能带有一定的常数).
  2. 设第i次操作的计算次数为xi,均摊后的计算次数为ai,则根据势能分析法,得ai=xi+Δφi(Δφi=φi-φ(i-1))
  3. 若为插入操作,则因线段树深度为O(logn),只需新增O(logn)个节点算上新增的左右空儿子数也是O(logn)的(乘了常数2),再加上本身O(logn)的实际计算复杂度,则总的复杂度还是O(logn),
  4. 若为合并操作,则有两种情况:
    • 当前节点为两棵要合并的树的共有的节点,则算法本身开交为O(1),因为使两节点合并成一个节点,所以对势能函数的贡献为-O(1),正负抵消,即均摊无开支(通过调整常数即可相消)
    • 当前节点为两颗树一颗有一颗没有的情况,则算法本身开销为O(1),因为新合并的线段树在此处少了一个空节点,所以对势能函数的贡献为-O(1),正负抵消,即均摊无开支(通过调整常数即可相消)
  5. 综上,Σxi+φn=Σai<=O(nlogn) 又因为φi的复杂度为O(nlogn),所以Σxi+O(nlogn)<=O(nlogn)(注意,此处是随机的,调整常数也不会抵消),即Σxi的复杂度为O(nlogn),线段树合并复杂度为O(nlogn),证毕