【算法设计与分析】08 序列求和的方法

小鱼儿 2024-04-19 08:01 44阅读 0赞

> 本篇文章学习数列求和的一些方法。这些方法对后面学习算法的时间复杂度非常有帮助。

### 文章目录 ###

*   *  1. 数列求和公式
     *   *  1.1 二分搜索的时间复杂度求解
     *  2 估计和式上届的放大法
     *  3 估计和式渐近的界
     *  4 总结

## 1. 数列求和公式 ##

下面这几个数列求和公式都是高中学过的公式。

*  等差、等比数列和调和级数

![在这里插入图片描述][20190915144641948.png]

下面给出一个求和的例子，使用了一些高中都会的变换的技巧：

![在这里插入图片描述][20190915145023891.png]

学习上面的公式，主要是为了解决算法的时间复杂度，下面以二分搜索的时间复杂度为例，讲解如何利用上面的公式求解出，时间二分搜索的时间复杂度（关于时间复杂度的概念，可以参看以前的文章：[【算法设计与分析】03 算法及其时间复杂度][03]）。

### 1.1 二分搜索的时间复杂度求解 ###

*  假设二分数组为T\[n\]，要搜索的数为：x。如下图是一个简单数组的搜索过程。

![在这里插入图片描述][20190915145705556.png]  
上述的二分搜索最终并没有找到要搜索的元素的位置。所以二分搜索的数据的输入情况，可以分为两种，一种是想要搜索的数x在数组中，一种是想要搜索的x不在数组中，那么一共就有2n+1中情况发生。如下图：

*  左边是x在数组中，可以在任何一个位置出现，有n种情况。
 *  右边是x不在数组中，那么x出现在数组的两边或者在数组中两个元素的中间，就有n+1种情况
 *  所以一共有2n+1种输入情况。  
    ![在这里插入图片描述][20190915145954476.png]

> 注意：上述，假设n=2k\-1,只是为了方便后面的计算。

现在已经知道了总的输入，还需要知道总的输入对应的比较的次数，才能计算出时间复杂度。  
由分析可以看出，比较t次的输入的个数为：

![在这里插入图片描述][20190915150724894.png]

所以：

*  对于t= 1，2…k-1，比较t次的输入有 ：2t-1 个 (这个对应的是x在数组中的情况)
 *  对于x不在数组中的情况，需要比较的次数是k，那么比较k次的输入就是：2k-1\+n+1个。（式子中的n+1是对应的不在数组中非空隙的个数，2k-1 对应的是x在数组中的情况，因为就算要找的数不在数组中，也要将数组比较完全一遍才能够知道）

那么总次数就等于：对每个输入乘以这个输入对应的次数并求和

假设n=2k\-1 ，各种输入的概率相等，则二分搜索平均时间复杂度为A（n）：

![在这里插入图片描述][2019091515230530.png]

上述的计算过程用到了一开始学习的几个公式以及变换技巧，自己慢慢掌握。

上述的计算结果大家都不陌生了，正式二分搜索的平均时间复杂度：logn

## 2 估计和式上届的放大法 ##

放大法在高中大家学的都很熟练应该。

*  放大法：

![在这里插入图片描述][20190915152544248.png]

*  放大法的例子

![在这里插入图片描述][20190915152644575.png]

## 3 估计和式渐近的界 ##

以下方法用到了基本微积分的概念。

求上届  
![在这里插入图片描述][20190915152820577.png]

求下届  
![在这里插入图片描述][20190915152906213.png]

上面的上届和下届都是同一个级别的，所以：

![在这里插入图片描述][20190915153050284.png_pic_center]

## 4 总结 ##

本文学习了序列求和的基本公式：

*  等差数列
 *  等比数列
 *  调和级数

对于无法计算的序列和，可以采用放大法求上届，用积分做和式渐近的界

这些基本的计算方法对计数循环过程的基本运算次数很有帮助。也就是算法的时间复杂度了。

[20190915144641948.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a740ab5ffca548b184067a360082da28.png
[20190915145023891.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f796f4c84bc840bfab4102f386941780.png
[03]: https://blog.csdn.net/qq_37375427/article/details/94031024
[20190915145705556.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e0bddbe39f254495b8ae798c090d7730.png
[20190915145954476.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e4e237c8c9aa470ab902b7a7d14f18cd.png
[20190915150724894.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/edefab27c371403c81703ef3b80d3a17.png
[2019091515230530.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7adcd88b08524106be793519bf75c50a.png
[20190915152544248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/60ae8c1a705147a1a4e735fa4cb8ef0f.png
[20190915152644575.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ce3d943fda984f9b9e9d79e398c9ee05.png
[20190915152820577.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b47c5bf3df6a4d39acc57f4119674536.png
[20190915152906213.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c865c7125ea444e2b0e52eff8e50bace.png
[20190915153050284.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ca801fb8669e4f51b7d01bfaa649aa95.png