求和

来自计算思维百科
跳转至: 导航搜索

当一个算法包含循环结构时,其运行时间可以表示成求和公式,如前面分析插入排序的最坏时间复杂度为1+2+…+n-1。因此,需要掌握一些常见的求和公式和求和方法。

首先给出和式定义。给定一个数列a1,a2,…,an,有限和a1+a2+…+an(n是非负整数)可以写成 RTENOTITLE

常见求和公式

常见的求和公式有等差级数、平方级数、等比级数等。

等差级数

RTENOTITLE

平方级数

 RTENOTITLE

k方和级数

  RTENOTITLE

等比级数

RTENOTITLE

调和级数

RTENOTITLE

算术-几何级数

RTENOTITLE

求和RTENOTITLE

    RTENOTITLE
           RTENOTITLE

确定求和公式的界

当然,并不是所有的求和公式都有精确值,但可以利用多种技术估计和式的上界。因算法分析主要关注的是函数的渐近界,因此上界的估计对算法分析而言也是有意义的。

估计和式上界的第一种方法是用数列中的最大项代替数列中的每个项,即表示为RTENOTITLE。例如,RTENOTITLE的一个可快速获得的上界是:RTENOTITLE这种方法虽然简单,但是放大后求得的和可能与原来数列的和差距很大。如果放大后求得和函数的渐近界仍旧保持不变,这种放大是有用的。

另一种放大方法用到等比级数。假设存在常数r(0<r<1)使得对任意的i≥0有ai+1/ai≤r则有:

RTENOTITLE

估计RTENOTITLE的上界

为使用等级级数放大法,将级数重写为i从0开始,得:

RTENOTITLE

对任意的i≥0,连续两项的比为:

RTENOTITLE

因此,有:

RTENOTITLE

除了用放大的方法之外,在求复杂求和公式的界时,还可以采用分割求和的方法,即将级数表示为两个或多个级数之和,然后再对每个级数分别求界。

估计RTENOTITLE的下界

RTENOTITLE

前面已有,RTENOTITLE。因此,RTENOTITLE

估计RTENOTITLE的上界

当i≥3时,连续两项的比率为:

RTENOTITLE

因此,采用分割求和的方法,得:                            

RTENOTITLE