前言
求递推关系式
- 例一汉诺塔
  - 算法简述
  - 求关系式
- 例二分治法求最大值
  - 算法简述
  - 求关系式
求时间复杂度
- 例一汉诺塔
- 例二分治法求最大值

前言

本文为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);
}

求关系式

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;
       }
}