算法分析(一)

算法分析记录

算法分析

递归与分治策略

分治策略:

将一个难以直接解决的大问题,分割成一些规模较小的相同子问题,各个击破,“分而治之”!

思路

  • 将要求解的问题划分为k个小问题
  • 然后对这个k个子问题进行递归求解
  • 最后合并子问题的解

递归概念

递归函数

用函数自身给出定义的函数称为递归函数

递归算法

直接或间接地调用自身的算法为递归算法

对于函数f(n)的递归定义,满足以下两个条件:

  • 基本部分:其中对于n的一个或多个值,f(n)必须是直接定义的(即非递归)
  • 递归部分:右侧所出现的所有f的参数都需有一个比n小,以重复运用递归部分来改变右侧出现的f,直至出现f的基本部分
典型递归问题
  • 斐波那契(Fibonacci)数列
  • 阿克曼(Ackerman)函数
  • 排列问题
  • 整数划分问题
  • Hanoi塔问题

未完待续…