时间复杂度

表示代码执行时间随主句规模增长的变化趋势，即：渐进时间复杂度。常用的方法：

1. 只关注循环执行次数最多的一段代码

单个循环时间复杂度是O(n)

2. 加法法则：

总复杂度等于量级最大的那段代码的复杂度
将代码块根据循环进行划分，然后计算每个部分的时间复杂度，再选取一个量级最大的作为整段代码的复杂度，举例如下：

  1. func f(n int) {
  2.     ...
  3.     // sum_1
  4.     for i:=0;i<100;i++ {
  5.         // todo 
  6.     }
  7.     ...
  8.     // sum_2
  9.     for i:=0;i<n;i++{
  10.         // todo 
  11.     }
  12.     ...
  13.     // sum_3
  14.     for i:=0;i<n;i++{
  15.         for j:=0;j<n;j++{
  16.             // todo
  17.         }
  18.     }
  19. }

分块分析：

sum_1 -> O(1)
sum_2 -> O(n)
sum_3 ->O(n^2)

最终时间复杂度为：

O(n^2)

3. 乘法法则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
如上述代码中sum_3部分的时间复杂度

4. 几种常见时间复杂度实例

  • O(1)

一般代码中不存在循环、递归语句，例如：i + j

  • O(logn)、O(nlogn)

举例：

var i = 1
for i < n {
    i = i * 3
}
  • O(m+n)、O(m*n)

这是因为无法判断m和n二者哪个量级大

空间复杂度

表示算法的存储空间与数据规模间的增长关系。
常见的有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)

其他几个概念

最好、最坏、平均、均摊时间复杂度