更新摊还分析方法分析时间复杂度

归并模板

归并属于分治算法，有三个步骤

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

待证问题: tmp 保存的是 q[l..mid] , q[mid+1..r] 中从小到大排序的所有数

证明(第一个 while 循环)

循环不变式: tmp[0..k-1] 保存上述俩数组中从小到大排序的最小 k 个数

1. 初始

   k = 0, tmp[0..k-1] 为空，显然成立

2. 保持

   假设某轮循环开始之前，循环不变式成立

   若 q[i] <= q[j], 则 tmp[k] = q[i]

   其中, q[i] <= q[i+1..mid], q[i] <= q[j] <= q[j+1..r]

   ∴ q[i] 是剩下的所有数中最小的一个

   当 q[i] > q[j] 时，同理可以得到 tmp[k] = q[j] 是剩下数中最小的一个

   ∴ tmp[k] 是剩下数中最小的一个

   ∴ k自增之后，下轮循环开始之前，tmp[0..k-1]保存从小到大排序的最小k个数

3. 终止

   i > mid 或 j > r

   则 q[l..mid] 和 q[mid+1..r] 其中一个数组的数都已遍历

   tmp[0..k-1]保存从小到大排序的最小k个数

边界分析

• 为什么不用 mid - 1 作为分隔线呢

  即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)

  因为 mid = l + r >> 1 是向下取整，mid 有可能取到 l (数组只有两个数时)，造成无限划分

  解决办法: mid 向上取整就可以了, 即 mid = l + r + 1 >> 1,如下所示:

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int mid = l + r + 1>> 1;//注意mid是向上取整
    merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r);

    int k = 0, i = l, j = mid, tmp[r - l + 1];
    while(i < mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i < mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];

}

不过最好不要这样写,很奇葩,不对称

• 为什么 用 mid 作为分隔线时不会造成无限划分呢

  因为此时 mid 是向下取整的, merge_sort(q, l, mid ) 中的 mid 一定不会取到 r 值

  ∴ merge_sort(q, l, mid ) 不会无限划分

摊还分析

摊还分析是一种分析时间复杂度的方法

主要有三种:

• 聚合分析(记账法)
• 核方法
• 势能法

聚合分析(记账法)最符合直观感觉,

聚合分析归并排序的时间复杂度

归并排序属于分治法, 很容易写出递归式:

$T(n) = 2T(n/2) + f(n)$

其中, $2T(n/2)$ 是子问题的时间复杂度, $f(n)$ 是合并子问题的时间复杂度

1.直观

直观上我们感觉 $f(n) = O(n)$, 事实也正是如何, 因为每次 while 都会把一个元素添加到数组中, 一共有 n 个元素, 所以 while 循环的次数为 n , 时间复杂度为 $O(n)$

2.摊还分析的聚合分析

对于每次迭代中选出并添加到数组中的元素, 我们给它的摊还代价设为 1(记账为 1)

一个元素只能计费一次, 因为马上就被添加到数组中了

一共有 n 个元素, 所以摊还总代价为 n, 算法的时间复杂度为 $O(n)$

摊还代价, 我们自己设定的一个理想代价, 只有一个要求: 总的摊还代价大于总的实际代价, 所以总摊还代价是总实际代价的上界

实际代价, 实际操作的代价

3.计算归并排序的递归式

得到 $f(n) = O(n)$ 后, 根据递推式的计算方法(代入法, 递归树法, 主方法)容易计算出 $T(n) = O(n\log n)$, 即归并排序的时间复杂度为 $O(n\log n)$

总结归并思路

1. 有数组 q, 左端点 l, 右端点 r

2. 确定划分边界 mid

3. 递归处理子问题 q[l..mid], q[mid+1..r]

4. 合并子问题

   1. 主体合并

      至少有一个小数组添加到 tmp 数组中

   2. 收尾

      可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中

   3. 复制回来

      tmp 数组覆盖原数组