你还在迭代和递归吗?
当你解决一个问题的时候,如果能够递归,你可能很快就写出一个简洁的程序。每当我们对自己新想出来的递归或迭代算法自我陶醉的时候,是否想过还有更加高效的算法?
其实大多数递归或迭代的问题都能转化为非递归算法。更厉害的算法复杂度可以降到O(1)。不信请看下面例子。
(2)一只青蛙一次可以跳上1级台阶,也可以跳上2 级……它也可以跳上n 级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?
毋庸置疑,第一个不就是斐波那契数列么。难道我们又要递归或者迭代了吗?那么第二个呢?要知道递归付出的时间是惨重的!其实很多递推公式都可以解成关于N的函数,这个在组合数学这门课中会详细介绍。
附上上面两个问题的代码:
double Fib(int n){ return (5 + sqrt(5.0)) / 10 * pow((1 + sqrt(5.0)) / 2, n) + (5 - sqrt(5.0)) / 10 * pow((1 - sqrt(5.0)) / 2, n); } double NB_Fib(int n){ return pow(2.0, n - 1); }
所以以后在遇到递归和迭代的时候,首先想想是否可解。切莫直接递归啊!