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

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

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

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

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

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

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

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

所以：

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

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

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

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

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

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

求上届

求下届

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

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

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

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