时间&空间复杂度

为什么要有复杂度分析

将代码多跑几遍，来测试性能的这种事后统计法存在一定的局限性
1 .测试结果依赖测试环境
2 .测试结果受数据规模影响大

大O复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增常的变化趋势，所以也叫渐近时间复杂度，简称时间复杂度
所有代码的执行时间T(n)与每行代码的执行次数f(n)成正比。即T(n)=O(f(n))。O代表代码的执行时间T(n)与f(n)表达式成正比

时间复杂度分析

1.只关注循环执行次数最多的一段代码
2 .加法法则：总复杂度等于量级最大的那段代码的复杂度
3 .乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
4.多个规模求加法：比如方法有两个参数控制两个循环次数，那么这时就取二者复杂度相加O(m+n)

常见时间复杂度分析

1. 常量阶 O(1)
   一般情况下，只要算法中不存在循环、递归，即使有成千上万的代码，其时间复杂度也是O(1)
2. 对数阶O(logn)

    for i := 1; i < n; {
        i = i * 2
    }

i=1;i=2;i=4;i=8....;i=n
2的x次方等于n，即x=log2(n)

3. 线性阶O(n)
4. 线性对数阶O(nlogn)
5. 平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)
6. 指数阶O(2n)

7. 阶乘阶O(n!)

   
   image.png

时间复杂度几种情况

1. 最好情况时间复杂度
   在最理想的情况下，执行这段代码的时间复杂度
2. 最坏情况时间复杂度
   在最糟糕的情况下，执行这段代码的复杂度
3. 平均时间复杂度
   加权平均时间复杂度
4. 均摊时间复杂度
   其实可以理解为平均时间复杂度

实例

var length = 2
var array = make([]interface{}, length);
var i = 0
func add(val interface{}) {
    if i >= length {
        array1 := make([]interface{}, length *2)
        for j :=0; j < length; j ++ {
            array1[j] = array[j]
        }
        length = length*2
        array = array1
    }

    array[i] = val
    i++
}

最好情况时间复杂度：为i<length。不执行if里O(1)
最坏情况时间复杂度：为i >=length。执行if里O(n)
平均时间复杂度：11/(n+1)+11/(n+1)+...+1*n/(n+1)=n/(n+1)+n/(n+1)=2n/(n+1)。即O(1)

空间复杂度

表示算法的存储空间与数据规模之间的增长关系。也叫渐近空间复杂度
只有在分配内存的时候才有空间复杂度的概念