算法分析法則,以及其他漸近符號
===
### 法則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)
