logN復(fù)雜度估算
logN復(fù)雜度的算法可以認(rèn)為具有以下特性：
用常數(shù)時(shí)間將問題的大小削減為某一部分（通常是1/2）
例如分治法求最大子串問題刹泄，將一個(gè)$O(N^{2})$的問題削減為每個(gè)的1/2震放，每個(gè)問題復(fù)雜度為$O(N)$（有循環(huán)）棠枉，所以該算法的復(fù)雜度估計(jì)為$O(NlogN)$
logN復(fù)雜度算法舉例
對(duì)分查找
問題
已知一串整數(shù)按順序排布壤靶，尋找某個(gè)指定數(shù)的下標(biāo)
求解
考慮已經(jīng)按順序排列，那么使用二分查找的方法即可全景。對(duì)于For循環(huán)內(nèi)部算法的復(fù)雜度是O(1)艾蓝，且每次循環(huán)都將問題縮小一半，所以認(rèn)為這是一個(gè)O(logN)的算法
func binary_search(data []int, target int) int {
left, right, mid := 0, len(data), 0
for left != right {
mid = int((left + right) / 2)
// fmt.Println(mid)
if data[mid] == target {
return mid
} else if data[mid] > target {
right = mid
} else {
left = mid
}
}
return -1
}
歐幾里德算法
歐幾里得算法是用于取最大公因數(shù)的算法（中國古代類似的算法好像是碾轉(zhuǎn)相除法粪牲？）古瓤。這個(gè)算法中，每次循環(huán)也是將問題變得更小
func gcd(a, b int) int {
rem := 0
for b > 0 {
rem = a % b
a = b
b = rem
}
return a
}
遞歸求冪
類似于二分查找腺阳，遞歸求冪的原理是$x^{2n} = x^{n} * x^{n}$相比于普通階乘落君，減少了乘法的次數(shù)。同時(shí)亭引，也是每次循環(huán)問題（N）減為原來的一半绎速，也是一個(gè)O(logN)復(fù)雜度問題
func pow(x, n int) int {
if n == 0 {
return 1
} else if n == 1 {
return x
} else if n%2 == 0 {
return pow(x*x, n/2)
} else {
return pow(x*x, n/2) * x
}
}
