【算法基础】归并排序算法的证明与边界分析

博主： Fivk
发布时间：2021 年 12 月 06 日
604 次浏览
暂无评论
518字数
分类：算法基础

#### 归并模板

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

1. **分成子问题**
2. **递归处理子问题**
3. **合并子问题**

```cpp
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` 作为分隔线呢

</div>

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

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

</div>

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

```cpp
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 作为分隔线时不会造成无限划分呢?

</div>

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

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

</div>

#### 摊还分析

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

主要有三种:

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

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

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

归并排序属于分治法, 很容易写出递归式:$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(nlogn)$, 即归并排序的时间复杂度为 $O(nlogn)$

作者：醉生梦死
链接：https://www.acwing.com/solution/content/16778/
来源：AcWing

</div>

版权声明 ▶ 本网站名称：Fivk博客
▶ 本文链接：https://blog.fivk.cn/archives/955.html
▶ 本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长进行核实删除。
▶ 转载本站文章需要遵守：商业转载请联系站长，非商业转载请注明出处！！
▶ 站长邮箱 admin@fivk.cn，如不方便留言可邮件联系。

最后修改：2021 年 12 月 06 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

null ？？［］
还可以把扩展运算符加上呀，这个很有用［…arr］，用于数组合...
null ？？［］
1
93攻略
你写得非常清晰明了，让我很容易理解你的观点。
ddd
您好，请问您有黑马探花交友虚拟机的资料吗
kkndtng
进阶

【算法基础】归并排序算法的证明与边界分析

Fivk • 2021 年 12 月 06 日

#### 归并模板

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

1. **分成子问题**
2. **递归处理子问题**
3. **合并子问题**

```cpp
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);

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` 作为分隔线呢

</div>

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

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

</div>

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

```cpp
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);

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

}
```

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

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

</div>

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

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

</div>

#### 摊还分析

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

主要有三种:

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

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

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

归并排序属于分治法, 很容易写出递归式:$T(n)=2T(n/2)+f(n)$

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

**1.直观**

**2.摊还分析的聚合分析**

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

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

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

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

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

作者：醉生梦死
链接：https://www.acwing.com/solution/content/16778/
来源：AcWing

</div>

【算法基础】归并排序算法的证明与边界分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【C】极域电子教室学生端解除控制

【JavaWeb】将项目搭建到服务器（有报错待解决）

【Java】类和对象

【数据结构】课前测试填空题1

【MySQL】数据库设计和多表操作

【探花交友】小视频方案

[函数快查] fopen -- 打开一个文件并返回文件指针

【数据结构】课前测试_哈夫曼编码

【C++】STL常用容器_stack容器

【Java】权限修饰符及关键字

【算法基础】归并排序算法的证明与边界分析

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【算法基础】归并排序算法的证明与边界分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款