算法2

算法的分类

1. 精确算法（exact algorithm），总能保证求得问题的解
2. 启发式算法（heuristic algorithm），通过使用某种规则，简化或智能猜测来减少问题求解时间。不能保证是问题的最优解，甚至不一定是问题的可行解（feasible solution）

PS:对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximation algorithm），求得的是问题的可行解，而不是最优解。

如何确认算法

• 如果一个算法对于所有合法的输入，都能在有限时间内输出预期的结果，那么此算法是正确的。确认一个算法是否正确的活动称为算法确认（algorithm validation）
• 使用数学方法证明算法的正确性，称为算法证明（algorithm proof）
  • 证明算法正确性常用的方法是数学归纳法
  • 要证明算法是不正确的，只要给出能够导致算法不能正确处理的输入即可

递归

• 递归，定义一个新事物、新概念或新方法，一般要求在定义中只包含已经明确或证明的事物、概念或方法。然而递归却不然，递归（recursive）定义是一种直接或间接引用自身的定义方法。
• 递归包含两个部分：基础情况和递归部分。

• 最著名的斐波那契数列出场

  • 算法2
    

    这是它的递归定义，至到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，数组都可以的

• 递归树可以用来描述递归程序的执行过程