前言

算法(algorithm),在数学和计算机科学之中,一个被定义好的、计算机可施行之指示的有限步骤或次序,常用于计算、数据处理和自动推理。作为一个有效方法,算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。
算法中的指令描述的是一个计算,当其运行时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。

eg1

从一个小时候大家都听过的故事开始,高斯老师留了一道题 1 + 100 的题让学生计算,普通学生的计算方法是从 1 一点点加到100,即时间复杂度为O(n):

const fun = function (n) {
  let ans = 0
  for(let i = 1; i <= n; i++) {
    ans += i
  }
  return ans
}
fun(100)

高斯的方法是首尾相加,用乘法乘上数量除以2,即时间复杂度为O(1):

const fun = function (n) {
  let ans = (1 + n) * n / 2
  if(n % 2) ans += (1 + n) / 2
  return ans
}
fun(100)

eg2

斐波那契数列是指每一项均为前两项之和的数列,标准的斐波那契数列为0,1,1,2,3,5,8,13,21,34,55,89,144,233 …
斐波那契数列问题有多种表述形式(马甲),常见的有以下几种

  • 兔子繁殖问题:农场里起初有一对兔子,每年繁殖一对小兔,小兔一年后成年,问n年后农场里一共有多少对兔子?
  • 跳台阶问题:小和尚从山脚下往山上跳台阶,每次可以跳一级或者两级台阶,问要跳到n级台阶,一共有多少种跳法?
  • 矩形覆盖问题:用n个2 * 1的小矩形无重叠地完全覆盖一个2 * n的大矩形,总共有多少种方法?

下面就来由简入深,一一讲解每种解法的实现及复杂度。

解法一:递归实现

/**
 * 递归实现,复杂度O(2^n)
 */
const f1 = function(n) {
  if (n <= 0) {
    return 0
  } else if (n == 1) {
    return 1
  } else {
    return f1(n - 2) + f1(n - 1)
  }
}

这种方式代码看起来很简洁优美,但实际上却是效率最低,复杂度最高的方法,包含了许多的重复计算,代码复杂度是O(2^n)。

理论上计算斐波那契数列第n项只需要n次运算即可得到,于是我们有了下面的第二种解法:

解法二:迭代实现

/**
 * 迭代实现,复杂度O(n)
 */
const f2 = function(n) {
  if (n <= 0) return 0
  let a = 0
  let b = 1
  for (let i = 1; i < n; i++) {
    b = a + b
    a = b - a
  }
  return b
}

到这里,我们去除了不必要的重复计算,将代码复杂度减少到了O(n)。

单纯从代码层面似乎没有太多可以优化的空间了,接下来让我们转变思维,从数学角度来思考一下:

解法三:矩阵实现

回到第二步的迭代实现,其实每一次迭代都是在做将a,b转化为b,a+b的计算,如果我们将其转化为矩阵,就有了以下公式:

将斐波那契数列代入这个公式,其最初的两项为a=0,b=1,我们可以得到

const f4 = function (n) {
  // 乘法
  const mul = function (x,y) {
    let ans = [[],[]]
    ans[0][0] = x[0][0] * y[0][0] + x[0][1] * y[1][0]
    ans[0][1] = x[0][0] * y[0][1] + x[0][1] * y[1][1]
    ans[1][0] = x[1][0] * y[0][0] + x[1][1] * y[1][0]
    ans[1][1] = x[1][0] * y[0][1] + x[1][1] * y[1][1]
    return ans
  }
  const fpow = function (x, n) {
    let ans = [[1, 0],[0, 1]]
    let y = x
    while(n) {
      if(n % 2){
        ans = mul(ans, y)
        n--
      }
      y = mul(y, y)
      n /= 2
    }
    return ans
  }
  if(n < 1) return 0
  let x = [[0, 1],[0, 0]]
  let y = [[0, 1],[1, 1]]
  return mul(x, fpow(y,n-1))[0][1]
}

console.log(f4(3))
console.log(f4(4))
console.log(f4(5))
console.log(f4(6))
console.log(f4(7))
console.log(f4(8))
console.log(f4(9))

以上就是斐波那契数列常用的解法,后两种代码复杂度同为O(log(n)),矩阵解法在代码实现上要麻烦些,可读性略低,具体使用看各位的喜好。