时间复杂度 （算法与数据结构系列 1）

数据结构的重要性：

• 面向过程编程的年代流行的一句话 程序 = 数据结构 + 算法，虽然不尽正确，但是可窥一二。
• 是阅读源码理解设计的必要基础。
• 是从 coder 到 programmer 转变的必经道路。
• 现实点说数据结构和算法是一线大厂面试的必要环节。

而想要学好数据结构先要搞清楚时间复杂度如何计算。如果复杂度都计算不清楚，如何判断自己写出的算法是优秀的呢？

常见时间复杂度：

O(1)：无论 n 如何变，只执行常数次

x = 10

O(n)：for 循环

for i = 0; i < n; i++ {
  ...
}

O(n²)：嵌套 for 循环

for i = 0; i < in; i++ {
  for j = 0; j < jn; j++ {
    ...
  }
}

O(2ⁿ)：斐波那契递归

func fib(n int) int {
  if n == 0 || n == 1 {
    return 1
  } else {
    return fib(n - 1) + fib(n - 2)
  }
}

这里理解可能稍微有点难度，可以把整个运算想象成一颗二叉树，n 每增加 1，也就是树的高度增加 1，最下层的节点个数相比上一层要 * 2，也就是总共需要运算 2ⁿ 次。

O(logⁿ)：二分查找法

这里可以理解为和 O(2ⁿ) 相反的思路，O(2ⁿ) 是 n 每增加 1，运算次数 *2，二分查找里 n 每增加 1，运算次数 /2。
2^k = n 相反即 k = log₂ⁿ = logⁿ

O(nlogⁿ)：O(n) 和 O(logⁿ) 嵌套

O(n!)：n! = n * (n - 1) * (n - 2) * ...

阶乘，也叫暴力遍历
比如写出 [1, 2, 3, 4, ..., n] 的全排列。

多种复杂度曲线图：

复杂度.png

多种复杂度组合的计算逻辑：取最大复杂度

O = O(n) + O(2ⁿ) + O(1)
那么 O = O(2ⁿ)

总结：

从O(nlogⁿ) 到 O(n)，从 O(n) 到 O(logⁿ) 都是巨大的性能提升，所以学习算法第一步就一定要学会计算时间复杂度。
当然能够正确的计算时间复杂度只是学好算法的数据结构的第一步，三分靠学习，七分靠练习，下一篇介绍 LeetCode，优秀的程序员学习数据结构和算法都在用的练习网站。

系列会持续更新，需要查看可以进我主页。
如有疑问或者发现错误和纰漏，请留言指正。