• 前言
• 求递推关系式
  • 例一 汉诺塔
    • 算法简述
    • 求关系式
  • 例二 分治法求最大值
    • 算法简述
    • 求关系式
• 求时间复杂度
  • 例一 汉诺塔
    • 扩展
    • 找规律
    • 大O表示法
  • 例二 分治法求最大值
    • 扩展
    • 找规律
    • 大O表示法

前言

本文为JMU22级软件算法分析考前复习而总结归纳，讲解时间复杂度的计算。
应该重点考察递归算法的拓展递归分析法。

分2步。一、求出递推关系式。二、设问题规模n=某个值，展开找规律合并下结论。

求递推关系式

例一 汉诺塔

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？（每次只能移动1个盘子，大盘子只能放在小盘子下面）。

算法简述

求把n个圆盘移到目标柱时：

• 1.把n-1个圆盘移到工具柱。
• 2.把最大盘移到目标柱。
• 3.把n-1个移到目标柱。

public static void hanoi(int nDisks,char  A,char B,char C){
        if (nDisks==1){ move(nDisks,A,C);return;}

        hanoi(nDisks-1,A,C,B);
        move(nDisks,A,C);
        hanoi(nDisks-1,B,A,C);
}

求关系式

• 我个人觉得最容易出错的就是有时候是+1，有时候是+n。后来发现最准确的方法是顺序分析算法到底做了什么，它的时间复杂度和问题规模是否有关。

n个圆盘的递推关系式用T(n)表示。
如果目前此步只剩移动1个圆盘，那么直接移动，不递归，时间复杂度就是执行一次移动的时间，为1。
如果不止一个，那么递归移动n-1个圆盘移到工具柱，时间复杂度就是T(n-1),接着把最大盘移到目标柱，时间复杂度=1，最后递归移动n-1个圆盘移到目标柱，时间复杂度就是T(n-1)。
所以有：

例二 分治法求最大值

算法简述

在长度为n的数组求最大值

• 拆成两半，分别求次最大值
• 2者比较，得出最大值

void FindMax (int *Array, int left, int right,int *max)
{
       if ((right - left) == 0)
       {
              *max = *min = Array[left];
       }
      else {
                     int max1, max2;
                     FindMinMax (Array, left, (right - left)/2 + left, &max1);
                     FindMinMax (Array, (right - left)/2+1 + left, right,&max2);
                     (min1 > min2) ? *min = min2 : *min = min1;
                     (max1 > max2) ? *max = max1 : *max = max2;
       }
}

求关系式

在长度为n的数组求最大值,递推关系式用T(n)表示。
拆成两半，分别求次最大值，时间复杂度就是2T（n/2）。然后2者比较，时间复杂度为1。
所以有：

求时间复杂度

例一 汉诺塔

上面我们已经求得递推关系式：

扩展

将递推关系式式拓展，就是不停带入关系式，一般写3层就行了：

找规律

写了3步就可以知道，n是一次次减到1为止，所以一共拓展n-1次（n-1到1），那么系数就是2的n-1次方，还要加上n项，首项为1，公比为2的等比数列。

大O表示法

大O表示法要忽略常量、低次幂和最高次幂的系数。
所以最后得到O(n的2次方)。

例二 分治法求最大值

扩展

带入表达式：

找规律

要一直递归到T(1)时才停，需要求出第几层，得出关系式 n/2的k次方 = 1 ，也就是k = logn。要递归logn层。那么T(1)的系数就是，2的k次方，也就是n，然后再加上k项，首项为1，公比为2的等比数列。

大O表示法

忽略常量和系数，得到O(n)复杂度。