算法的分类
- 精确算法（exact algorithm），总能保证求得问题的解
- 启发式算法（heuristic algorithm），通过使用某种规则，简化或智能猜测来减少问题求解时间。不能保证是问题的最优解，甚至不一定是问题的可行解（feasible solution）
PS:对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximation algorithm），求得的是问题的可行解，而不是最优解。
如何确认算法
- 如果一个算法对于所有合法的输入，都能在有限时间内输出预期的结果，那么此算法是正确的。确认一个算法是否正确的活动称为算法确认（algorithm validation）
- 使用数学方法证明算法的正确性，称为算法证明（algorithm proof）
- 证明算法正确性常用的方法是数学归纳法
- 要证明算法是不正确的，只要给出能够导致算法不能正确处理的输入即可
递归
- 递归，定义一个新事物、新概念或新方法，一般要求在定义中只包含已经明确或证明的事物、概念或方法。然而递归却不然，递归（recursive）定义是一种直接或间接引用自身的定义方法。
- 递归包含两个部分：基础情况和递归部分。
-
最著名的斐波那契数列出场
-
图片发自简书App
这是它的递归定义，至到18世纪前，人们一直都只能采用递归定义来计算，它的直接计算公式太复杂了，看不懂，这里就不贴了。
- 代码实现
-
uint64_t Fib(uint64_t n)
{
if (n<=1) return n;
return Fib(n-1)+Fib(n-2);
}
挺简单的，是吧，但是，对，这种话后面一般都有但是
这个程序如果真的执行，最多也就到n=40左右，50基本上就看不到结果了，或者要等很久，因为递归嵌套太深了，所以，还要优化，
map<uint64_t, uint64_t> g_mapFib;
uint64_t Fibex(uint64_t n)
{
if (n<=1){
return n;
}
uint64_t t = g_mapFib[n];
if (0 == t){
t = Fibex(n-2) + Fibex(n-1);
g_mapFib[n] = t;
}
return t;
}
使用map把计算过的值存起来，避免重复计算，然后速度就很快啦
这里用map纯粹是图方便，用vector，数组都可以的
- 递归树可以用来描述递归程序的执行过程
