时间复杂度和空间复杂度分析

http://www.zhihu.com/question/21387264

Big O notation （大O表示法）

• O(1)：Constant Complexity（常数复杂度）
• O(logn)：Logarithmic Complexity（对数复杂度）
• O(n)：Linear Complexity（线性时间复杂度）
• O(n^2)：N square Complexity（平方）
• O(n^3)：N cubic Complexity（立方）
• O(2^n)：Exponential Growth（指数）
• O(n!)：Factorial（阶乘）

注意：只看最高复杂度的运算。抹掉系数

常数复杂度

无论N为多少，不存在循环递归的话顺序执行就是O(1)

// O(1)
int n = 1000
System.out.println("Hey - your input is：" + n)

// O(1)
int n = 1000
System.out.println("Hey - your input is：" + n)
System.out.println("Hmm.. I'm doing more stuff with：" + n)
System.out.println("And more：" + n)

线性时间复杂度

N的执行不存在嵌套循环，且循环次数为变量时，可以记为O(N)

// O(N)
for(int i = 1; i <= n; i++) {
    System.out.println("Hey - I'm busy looking at：" + i)
}

平方时间复杂度

双层嵌套循环：

// O(N^2)
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println("Hey - I'm busy looking at：" + i + "and" + j)
    }
}

立方时间复杂度

三层嵌套循环：

// O(N^3)
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        for(int k = 1; k <= n; k++) {
            System.out.println("Hey - I'm busy looking at：" + i + "and" + j + 'and' + k)
        }
    }
}

对数复杂度

函数体执行次数永远是它自己的 log2(N) 次，然后忽略常数

// O(log(n))
for(int i = 1; i <= n; i = i * 2) {
    System.out.println("Hey - I'm busy looking at：" + i)
}

指数复杂度

// O(k^n)
function fib(n) {
    if (n < 2) {
      return n
  }
  return fib(n - 1) + fib(n - 2) 
}

时间复杂度曲线

• N 比较小 (N < 5)，复杂度差不多
• N扩大，指数级别复杂度飞涨
• 如果写程序能降低时间复杂度，N 越大收益越高。如果时空复杂度增加，则资源消耗增加

总结：

1. 要对自己程序的时间和空间复杂度有所了解，
2. 如果用最简洁的时空复杂度完成程序的话，基本上是一个顶尖选手必备的职业素养。

例题

计算：1 + 2 + 3 + 4 + 5 + … + N 的和

方法一: 从1 - N循环累加。时间复杂度为 O(N)（亲测如果数字过大，浏览器会卡死）

let y = 0;
for(let i = 0; i < n; i++) {
    y += i
}

**
方法二：求和公式。时间复杂度为 O(1)

let y = n * (n + 1) / 2

**

计算：斐波那契数列 0 1 1 2 3 5 8 13 21 …

方法一： F(n) = F(n - 1) + F(n - 2) ⚠️ 面试禁用

function fib(n) {
    if (n < 2) {
      return n
  }
  return fib(n - 1) + fib(n - 2) 
}

以计算 fib(6) 为例，将其递归树形结构展开后如下图。我们看到，不仅计算树非常深，而且有很多重复计算的项目。如 **f(3) ， f(2) ， f(1)** 等。

可以加缓存，将计算过的结果缓存下来。**

主定理

主定理是为了解决所有递归的函数，如何计算他的时间复杂度问题。
http://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86

• 二分查找：O(logn)
• 二叉树遍历：O(n)
• 二维矩阵：O(n)
• 归并排序：O(nlogn)

例题

二叉树前序，中序，后序的时间复杂度为多少？

答：O(n)，n为二叉树节点总数。因为每个节点都会访问且仅访问一次，所以线性于二叉树节点总数。

图的遍历时间复杂度多少

答：O(n)。图节点都会访问且仅访问一次。n为节点总数

搜索算法DFS BFS时间复杂度多少

答：O(n)。每个搜索到的节点都只访问一次。n指搜索空间内的节电总数

二分查找时间复杂度多少

答：O(logn)

空间复杂度

• 数组长度
• 递归深度
• 如果有数组且有递归，用两者最大值作为空间复杂度

例题

leetcode：爬楼梯问题