聊聊算法思路

思路

在世上，人们解决问题的方式归为两种

人类思路：根据生活归纳出来的，人们根据生活经验，总结提炼
数学思路：根据数学推理归纳，通过对应的数学公式/定理，得出的结论

人类思路

把人类的思考流程翻译成代码，就是算法

人类思路求解最大值，一般利用遍历，从左到右扫描寻找最大值。
但是实际上，一堆数字，人们也可能直接看出最大值，比如有一个9999鹤立鸡群

  const array = [23,99,17,28,84]
  function max(array){
    let result = array[0]
    for(let i = 1; i< array.length; i++){
      if(array[i] > result){
        result = array[i]
      }
    }
  }
  max(array) // 99

如何证明算法是对的？

经验

按照一般人的逻辑和经验，这个算法是对的

无法给出反例，说明这个算法是对的

通过大量的测试，发现这个算法可以满足需求

大部分程序员只需要能满足需求的代码，而不是正确的代码，非科班的程序员一般使用的解题思想

有时候，这种人类思维，因为逻辑或者认知不够严谨，在未来也会被郑面是错误的。比如最早以前人们认为地球是平的，直到后来又有了日心说。人类思路就是在不断的利用经验得出结论，再推翻再结论的过程

数学思路

完全归纳法：数学家们喜欢利用公式和定理，一步步推理得出解法，而这样的解法是具有说服力的，只要公式定理以及推理过程是没有瑕疵的，那么结论一定是对的。

但是数学思路带来的弊端也是很明显，就是需要很强的逻辑能力。回忆一下高中数学物理老师最爱说的就是：显然，我们可以得出这个结论。而如果我显然不出来，那基本是凉凉了。

还是这个例子，选出最大值，通过完全归纳法我们可以得出下面的数学公式：

                     n1,(k=1)
max(n1,n2,...,nk){
                     nk>max(n1,n2,...,nk-1)? nk:max(n1,n2,...,nk-1),(k=2,3,...)

一旦有了数学公式，我们发现可以很轻易的转化成代码,但仔细一看会觉得，这什么鬼也太难懂了吧。没错，这就是数学思想。难懂，但好像的确是对的。

  const array = [23,99,17,28,84]
  function max(array){
  if(array.length === 1) { return array[0] }
  const otherMax = max(array.slice(1))
    return array[0] > otherMax ? array[0] : otherMax
  }
  max(array) // 99

可以发现，其实这就是递归，数学家们擅用递归来解决问题，我们也只是将定理公式代码化了。

如何证明数学算法是对的？

首先证明公式是对的（较难）

回忆一下高中数学，我们经常用代入法和举例法证明公式是对的，其实

max([23,99,17,28,84])
= m(23,max([99,17,28,84]))
= m(23,m(99,max([17,28,84])))
= m(23,m(99,m(17,max([28,84]))))
= m(23,m(99,m(17,m(28,max([84]))))
= m(23,m(99,m(17,m(28,84)))
= m(23,m(99,m(17,84)
= m(23,m(99,84)
= m(23,99)
= 99

通过代入法，你就会发现这就是递归，先递进，再回归的感觉，>型回调地狱

然后证明代码和公式等价

这一步就是用代码翻译一下了（简单）

总结

数学方法更容易通过形式化证明保证代码的正确性

但数学方法效率不一定高（但可以优化）

数学方法往往不够直观，普通人没有什么数学知识

一般不对变量进行二次赋值，因为数学里没有

对比

数学思路更注重形式（结构）

往往更加优雅/简单
更容易优化
投身于数学，有无线广阔的可能性

人类思维更注重过程（命令）

往往更容易执行、被理解
对人脑的负担更重
被人类的经验所局限

总结

复杂度守恒：复杂度不会因为任何原因降低
取决于把复杂度放在人脑这边，还是机器那边
实际上，我们可以结合两种思路，各取所长

遍历/递归/迭代

现在我们似乎可以简单的归纳

人类思路 ~ 遍历
数学思路 ~ 递归

遍历这边就不说了，因为大多数同学在写代码时，用的最多的就是for循环，所以人类思想不需要去特意修炼，顺着感觉写就可以。

接着借汉诺塔问题说说递归，汉诺塔是什么问题呢

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。（据说当都移完了以后，已经世界末日了，因为实在太久了）

image

那这个问题，靠直觉或者经验求解（人类思路）简直就是太难了，一般我们遇到这种问题，都会看一下答案，哦！然后恍然大悟。

简单理解为，把A上面的N-1个移动到B，然后把最大的移动到C，最后把B上面的N-1个移动到C，就结束了...
但是为了做到上面这一步，你需要先把A上面的N-2个移动到C，然后把最大的移动到B，最后把C上面的N-1个移动到B...
然后你就发现你的人类思维已经想不过来了，因为实在太多步了。

数学归纳法

证明当n=1时命题成立
证明如果n=k时命题成立，那么n=k+1时命题也成立（k=1,2,3...）

看着答案我们得出公式：

                     AC,(n=1)
h(n,A,B,C){
                     h(n-1,A,C,B) + AC + h(n-1,B,A,C)

通过一堆高中数学的应用题经验，我们其实也可以推出上面这个答案，不过显然，数学没有学好。

好在可以轻易的转为代码，然后我们验证一下啊，果然似乎是对的。

  h = (n, from, cache, to) =>
    n === 1 ? `${from}${to}` :
      h(n-1, from, to, cache) + ',' + `${from}${to},` + 
      h(n-1, cache, from, to)

通过汉诺塔问题，我们可以得出一些结论，在有些场景，巧妙的使用数学思想，是可以巧妙的解决一些似乎常规思想想象不到的问题，于是可以理解了为什么数学家那么少那么伟大，确实太烧脑了

现在我们尝试研究一下斐波那契数列

既然数学思想牛逼，那直接来递归搞起

// 数学思路：递归
  f = n =>
    n === 0 ? 0 :
    n === 1 ? 1 :
      f(n-1) + f(n-2)

看起来的确简单也好理解，但是当我用浏览器控制台尝试跑一下f(45)/f(46)/f(47),似乎感觉不太好了，因为实在是太慢了，你可以试试f(100),我反正是没有勇气的

那现在再来看看人类思路，循环

// 人类思路：循环
  f = n => {
    const array = [0,1]
    for(let i=2; i<=n; i++){
      array[i] = array[i-1] + array[i-2]
    }
    return array[n]
  }

不必说，人类的白话形式本身在理解层面就有优势，那执行速度呢，f(45)/f(46)/f(47)直接都是秒出的，完全没感觉到计算时间

斐波那契问题也巧妙了解释了，不是数学思想就一定是最棒的思想，有些问题，数学家想的过于复杂，设计的过于巧妙，导致产生了更多的时间复杂度。而用人类思想，反而解的很轻松。

为什么递归的时间效率会这么慢呢，这是为什么呢？

栈

递归需要使用栈

前面说到递归是先递进再回归，所以他可以巧妙用到栈这个数据结构，压栈时，把当前函数所在的环境变量压入，待回归时，把对应的环境弹出来
栈有长度限制

栈其实是有长度限制的，如果溢出了，我们通常称之为stackoverflow，每个引擎每种语言，栈的大小都是不定的。正常代码中也是需要考虑到爆栈问题
压栈和弹栈

提供了pop和push API的list就可以称之为栈

回到刚才的问题，为什么递归计算汉诺塔就特别慢，我们就可以从栈的思维推敲一下，如何有效减小压栈？

不用递归，所有的递归都可以写成循环

就是转成人类思维，所有的数学思维都是可以转人类思维的，只是你想不想的来的问题

// 循环代替递归

// 递归
f = n =>
  n === 1 ? 1 :
            n * f(n-1)
// 循环
  f = n => {
    let result = 1
    for(let i = 1; i <= n; i++){
      result = result * i
    }
    return result
  }

尾递归

尾递归的意思就是递归只出现在return语句且return语句里只有递归

//普通递归
f = n =>
  n === 1 ? 1 :
            n * f(n-1)

// 这里的4就是环境变量，每次压栈，导致弹栈的时候需要找到这个变量
f(4)
= 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * 2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

// 尾递归，没有旧状态
f(4)
= f(1,4,1)
= f(2,4,2)
= f(3,4,6)
= f(4,4,24)
= 24

递归需要归，尾递归不需要归

尾递归 -> 迭代

在这里，为方便理解，我们简单的给尾递归一个新定义，迭代。当然迭代还分好几种，如循环迭代，尾递归迭代。目前只讨论尾递归。

顾名思义，迭代可以理解为一种自我进化，带着旧的状态进化成了一种新的状态，进化后，就不再保留旧状态。也不再需要所谓的“归”

尾递归压栈: 因为不同语言不同客户端表现不一致，所以要提一下

形如：function a() { return b() } 这样就是一种尾递归或者说是尾递归迭代，由a函数完全到了b函数

在b()算出结果后，不需要任何其他操作，直接去a改返回的地方，所以为什么其实可以干脆省掉中间的压栈，在某些语言中，的确是这样的

不过缺点也有，平时我们都关注函数调用栈，如果以为这种尾递归调用而丢失了调用历史，那么debug将是一种灾难

这里查了一些资料，不同语言不同客户端在优化上表现不一致，就JavaScript来说

Chrome的v8没有实现尾调用优化
safari却实现了

缓存

尾递归是优化递归的一个方法，另一个方法就是缓存了

在刚才例子中，相信大家都看出来了，为什么人类思想的计算时间那么快，并不是因为本身多先进，只是因为人类会自然而然的使用缓存来加速计算，而数学公式却不会

就斐波那契问题，我们试试f(6)的计算次数：

f(5)一次，f(4)两次，f(3)三次，f(2)五次，f(1)和f(0)共11次，左右相加11次，总共33次操作。而这仅仅只是f(6)，所以我们刚才试图运行f(45)，想象一下是多么的灾难

f = n =>
   n === 0 ? 0 : n === 1 ? 1 : mf(n-1) + mf(n-2)
   
memorize = fn => {
  cache = {}
  return (first, ...args) => {
    if(!(first in cache)){
      cache[first] = fn(first, ...args)
    }
    return cache[first] 
  }
}

mf = memorize(f)

这次我们使用一个cache增强一下f函数，再试试你就会发现计算速度大大加快了，而且这个增强函数是无痛的，是不是就有点像平时我们用的缓存AOP原型了

但是，再往深层的想，你用了cache，那无非又回到了那个深奥的结论，时间换空间罢了~

总结

聊了这么多，人类思路或数学思路也好。其实写代码的时候，都是我们避不开的解法。作为人类，我们往往还是会使用直觉最优解。只是在这里，强行将两种解法抽象开了，并做了对比。一旦拨开云雾，就豁然开朗，感受着代码的魔力，感受着一切有因果。无非时间换空间，空间换时间罢了。