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

博主： Fivk
发布时间：2021 年 12 月 06 日
1201 次浏览
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>

最后修改：2021 年 12 月 06 日

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

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

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>

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

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

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

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【前端笔记】Vue3

【JavaWeb】HTTP&Tomcat&Servlet

【SpringCloud】Nacos 集群搭建

【动态规划】完全背包

【开发技巧】Vue2中如何优雅地实现dialog的封装

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