为什么要有复杂度分析
将代码多跑几遍，来测试性能的这种事后统计法存在一定的局限性
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)
常见时间复杂度分析
- 常量阶 O(1)
一般情况下，只要算法中不存在循环、递归，即使有成千上万的代码，其时间复杂度也是O(1) - 对数阶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)
- 线性阶O(n)
- 线性对数阶O(nlogn)
- 平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)
- 指数阶O(2n)
-
阶乘阶O(n!)
image.png
时间复杂度几种情况
- 最好情况时间复杂度
在最理想的情况下，执行这段代码的时间复杂度 - 最坏情况时间复杂度
在最糟糕的情况下，执行这段代码的复杂度 - 平均时间复杂度
加权平均时间复杂度 - 均摊时间复杂度
其实可以理解为平均时间复杂度
实例
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)
空间复杂度
表示算法的存储空间与数据规模之间的增长关系。也叫渐近空间复杂度
只有在分配内存的时候才有空间复杂度的概念
