logN复杂度估算
logN复杂度的算法可以认为具有以下特性：
用常数时间将问题的大小削减为某一部分（通常是1/2）
例如分治法求最大子串问题，将一个$O(N^{2})$的问题削减为每个的1/2，每个问题复杂度为$O(N)$（有循环），所以该算法的复杂度估计为$O(NlogN)$
logN复杂度算法举例
对分查找
问题
已知一串整数按顺序排布，寻找某个指定数的下标
求解
考虑已经按顺序排列，那么使用二分查找的方法即可。对于For循环内部算法的复杂度是O(1)，且每次循环都将问题缩小一半，所以认为这是一个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
}
欧几里德算法
欧几里得算法是用于取最大公因数的算法（中国古代类似的算法好像是碾转相除法？）。这个算法中，每次循环也是将问题变得更小
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}$相比于普通阶乘，减少了乘法的次数。同时，也是每次循环问题（N）减为原来的一半，也是一个O(logN)复杂度问题
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
}
}
