首页 > 代码库 > 算法学习笔记 递归之 快速幂、斐波那契矩阵加速

算法学习笔记 递归之 快速幂、斐波那契矩阵加速

递归的定义

原文地址为:http://blog.csdn.net/thisinnocence

递归和迭代是编程中最为常用的基本技巧,而且递归常常比迭代更为简洁和强大。它的定义就是:直接或间接调用自身。经典问题有:幂运算、阶乘、组合数、斐波那契数列、汉诺塔等。其算法思想:

  • 原问题可分解子问题(必要条件);
  • 原与分解后的子问题相似(递归方程);
  • 分解次数有限(子问题有穷);
  • 最终问题可直接解决(递归边界);

对于递归的应用与优化,直接递归时要预估时空复杂度,以免出现用时过长或者栈溢出。优化递归就是以不做重复的事儿为原则进行。对于常见数列问题,常常会有递推公式,也即 f(n) 和 f(n-1) 的关系式,由递推公式其实就很容易写出递归算法的代码,这里要重新详细说一下递归和递推的区别:

  • 递归:将问题规模为n的问题,降解成若干个规模为n-1的问题,依次降解,直到问题规模可求,求出低阶规模的解,代入高阶问题中,直至求出规模为n的问题的解, ( n  ->  0);
  • 递推:构造低阶的规模(如规模为i,一般 i=0 ) 的问题,并求出解,推导出问题规模为i+1的问题以及解,依次推到规模为n的问题, (0  ->  n);

快速幂


直接转换成代码,时间复杂度由朴素幂运算的 O(n) -> O(logn) :

/* a 的  n 次方的快速幂,C 代码 */
int quickpower(int a, int n) {
	if (n == 0)
		return 1;

	if (n % 2 == 1)
		return quickpower(a, n / 2) * quickpower(a, n / 2) * a;
	else
		return quickpower(a, n / 2) * quickpower(a, n / 2);
}

斐波那契数列


转换为代码,时间复杂度由直接递归的 O(n^2) -> O(logn) , 下面的实验用 Python 实现,如果用 C++ 重载乘法运算符,则可以很大程度复用快速幂代码了就:

import time

# 递归计算斐波那契数列 
def fib1(n):
    if n <= 1 :
        return 1
    else :
        return fib1(n - 1) + fib1(n - 2)

# 计算 a, b (都是 2×2 的矩阵) 的乘积 
def mul(a, b):
    r = [[0, 0], [0, 0]]
    r[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    r[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    r[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    r[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return r;

# 递归加速计算斐波那契数列 O(n^2) -> O(logn)
def fib(n):
    if n == 0:
        return [[1, 0], [0, 1]]
    if n == 1:
        return [[1, 1], [1, 0]]
    if n % 2 == 0 :
        return mul(fib(int(n / 2)), fib(int(n / 2)))
    else:
        return mul(mul(fib(int(n / 2)), fib(int(n / 2))), [[1, 1], [1, 0]])

if __name__ == '__main__':
    starttime = time.clock()
    print(fib1(35))  
    endtime = time.clock()
    print('直接计算用递归:', endtime - starttime)
    starttime = time.clock()
    print(fib(35)[0][0])
    endtime = time.clock()
    print('矩阵递归幂加速:', endtime - starttime)

''' 
实验运行结果:
14930352
直接计算用递归: 5.518564929662471
14930352
矩阵递归幂加速: 0.0002042703426949899
'''