算法补充知识

递归

递归，是一种解决问题的方法。通过解决问题的各个小部分，直到解决最初的大问题。通常涉及函数调用自身。

JavaScirpt 调用栈大小的限制

• 如果如果加上用以停止函数递归调用的边界条件，递归不会无限地执行下去。浏览器会抛出错误，也就是栈溢出错误（stack overflowerror）
• ES 6 有尾调用优化（tail call optimization）
  • 如果函数内最后一个操作是调用函数，
  • 会通过 ”跳转指令“（jump）而不是 ”子程序调用“ （subroutine call ）来控制
  • 也就是说，ES 6 中，这里的代码可以一直执行下去

斐波那契数列

定义

• 1 和 2 的斐波那契数是 1
• n ( n > 2 ) 的斐波那契数是 ( n - 1 ) 的斐波那契数加上 ( n - 2 ) 的斐波那契数

// 递归实现
function fibonacci( num ) {
    if ( num === 1 || num === 2 ) {
        return 1;
    }

    return fibonacci( num - 1 ) + fibonacci( num - 2 );
}

// 非递归的方式
function fib ( num ) {
  
        var n1 = 1,
            n2 = 2,
            n = 1;

        for ( var i = 3; i < num; i++ ) {
            n = n1 + n2;
            n1 = n2;
            n2 = n;
        }
  
        return n;
    }

• 递归并不比普通版本更快，反倒更慢
  • ES 6 中，因为尾调用优化的缘故，递归不会更慢
  • 但在其他语言中，递归通常更慢
• 递归更容易理解，代码量更少

动态规划（Dynamic Programming, DP ）

• 是一种将复杂问题分解成更小的子问题来解决的优化技术
• 用动态规划解决问题的例子
  • 深度优先搜索
  • 斐波那契问题
• 动态规划和分而治之（归并排序和快速排序算法中用到的那种），是不同的方法
  • 分而治之，把问题分解成相互独立的子问题，然后组合它们的答案
  • 动态规划，是将问题分解成相互依赖的子问题
• 用动态归化解决问题时，遵循三个重要步骤：
  • 定义子问题
  • 实现要反复执行而解决子问题的部分
  • 识别并求解出边界条件
• 能用动态规划解决的一些著名的问题
  • 背包问题
    • 给出一组项目，各自有值和容量
    • 目标是找出总值最大的项目的集合
    • 问题的限制是，纵容狼必须小于等于“背包”的容量。
  • 最长公共子序列
    • 找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余下元素的顺序而得到）
  • 矩阵链相乘
    • 给出一系列矩阵，
    • 目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）
    • 相乘操作不会进行，解决方案是找到这些矩阵各自相乘的顺序
  • 硬币找零
    • 给出面额为 d1...dn 的一定数量的硬币和要找零的钱数，
    • 找出有多少种找零的方法
  • 图的全源最短路径
    • 对所有顶点对（u, v），
    • 找出从顶点 u 到顶点 v 的最短路径

例子：最少硬币找零问题

function MinCoinChange(coins) {
    var coins = coins;
    var cache = {};

    this.makeChange = function (amount) {
        var me = this;

        if ( !cache[amount] ) {
            return [];
        }

        if ( cache[amount] ) {
        return cache[amount];
        }

        var min = [],
            newMin,
            newAmount;
        
        for (var i = ; i < coins.length; i++) {
            var coin = coins[i];
            newAmount = amount - coin;

            if (newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            }

            if (
                    newAmount >= 0 &&
                    (newMin.length < min.length - 1 || !min.length) &&
                    (newMin.length || !newAmount)
                ) {
                    min = [coin].concat(newMin);
                    console.log("new Min" + min + " for " + amount);
            }
        }
    };
}

贪心算法

• 遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。不像动态规划那样计算更大的格局
• 比起动态规划，贪心算法更简单、更快
• 贪心算法并不是总能得到最优解
• 最少硬币找零问题

// 思路
// 从最大面额的硬币开始，那尽可能多的这种硬币找零
// 当无法再拿更多这种价值的硬币时，开始拿第二大价值的硬币，依次继续

// 对每个面额（从大到小），把它的值和 total 相加后，
// total 需要小于 amount 
// 将当前面额 coin 添加到结果中，也会将它和 total 相加

function MinCoinChange ( coins ) {
    var coin = conins;

    this.makeChange = function ( amount ) {
        var change = [],
            total = 0;

        for ( var i = coins.length; i >= 0; i--) {
            var coin = coins[i];

            while ( total + coin <= amount ) {
                change.push(coin);
                total += coin;
            }
        }

        return change;
    };
}

大 O 表示法

大 O 表示法 用于描述算法的性能和复杂程度