算法分析法则,以及其他渐近符号
===
### 法则1 for循环
> 建设循环体的时间复杂度为O(n),循化次数为m,则这个循环的时间复杂度为O(n*m)
```
for i:=0;i<n;i++ {
fmt.Println(i)
}
```
循环n次,循化体时间复杂度为O(1) 总时间复杂度为O(n*1) = O(n)
### 法则2 嵌套的for循环 (法则2为法则1的扩展)
> 对于多个循环,假设循环体的时间复杂度为O(n),各个循环次数分别为a,b,c..,
> 则这个循环的时间复杂的为O(n*a*b*c..)
> 分析的时候应该往外分析这些循环
```
for a:=0;a<n;a++{
for b:=0;b<x;b++ {
fmt.Printf("a:%d b:%d \n",a,b)
}
}
```
时间复杂度O(n*x*1) = O(nx)
### 法则3
> 各个语句的运行时间求和即可(或者说取较大值)
~~~
// 第一部部分时间复杂度为 O(n)
for i:=0;i<n;i++ {
fmt.Println(i)
}
// 第二部分时间复杂度为O(n^2)
for i:=0;i<n;i++ {
for b:=0;b<n;i++ {
fmt.Println(i)
}
}
~~~
时间复杂度O(n + n^2) = O(n^2)
### 法则4 if/else语句
> 总时间复杂度等于其中时间复杂度最大的路径时间复杂度
~~~
// 第一部分时间复杂度O(n)
if flag >= 0 {
for a:=0;a<n;a++ {
fmt.Println(a)
}
// 第二部分时间复杂度O(n^2)
}else{
for a:=0;a<n;a++ {
for b:=0;b<n;b++ {
fmt.Println(b)
}
}
}
~~~
最大路径时间复杂度为O(n^2) 所以次代码的时间复杂度为O(n^2)
