matrix.md

矩阵

矩阵其实就是二维数组，但是我之所以分开，原因就是矩阵自成一派，用矩阵解决的东西是一个单独的系统.

矩阵长什么样子呢？

1 2

5 7

这就可以当作一个基本的矩阵，我们上大学的时候都学过高等数学里的线性代数，线代里 矩阵相乘用到算法中也是极好的。

矩阵相乘

斐波那契数列的log n解法

我们知道这么一个特性：

f(n) = f(n-1) + f(n-2)

fn         1      1              f(n-1)
     =                    x         

f(n-1)    1        0              f(n-2)

即： 1 * f(n-1) + 1 * f(n-2) = fn 下面的那个 1 * f(n-1) + 0 * f(n-2) = f(n-1)

然后同理可得

f(n-1)         1      1              f(n-2)
       =                    x         

f(n-2)        1        0              f(n-3)

推出

矩阵： fn 1 1 1 1 1 f(n-1) = * ... *
1 0 1 0 1

所以这道题变成了 这样 fx = m^n-1 这个类型了。 这样 这道题就从n的时间复杂度变成了logn （可以使用分治的方法）提升纬度 就是可以压缩时间。

// y = m ^ n-1

func Pow(x,n int) int {
  // 首先先判断边界和错误值。
  if n < 1 {
    return 1
  }
  if n < 0 {
    return 1/Pow(x, -n)
  }
  if n & 1 == 1 {
    return n *Pow(x,n-1)
  }
  return Pow(x*x,n/2)

}

// 非递归版
func Pow(x,n int)int{
  result := 0
  if n < 0 {
    n = -n
    x = 1/x
  }
//
  for n > 0 {
    if n & 1 == 1 {
      result *= x
    }
    x *= x
    n >>= 1
  }
//
  return result
}