logN复杂度估算

logN复杂度的算法可以认为具有以下特性：

用常数时间将问题的大小削减为某一部分（通常是1/2）

例如分治法求最大子串问题，将一个$O(N^{2})$的问题削减为每个的1/2，每个问题复杂度为$O(N)$（有循环），所以该算法的复杂度估计为$O(NlogN)$

logN复杂度算法举例

对分查找

问题

已知一串整数按顺序排布，寻找某个指定数的下标

求解

考虑已经按顺序排列，那么使用二分查找的方法即可。对于For循环内部算法的复杂度是O(1)，且每次循环都将问题缩小一半，所以认为这是一个O(logN)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
}

欧几里德算法

欧几里得算法是用于取最大公因数的算法（中国古代类似的算法好像是碾转相除法？）。这个算法中，每次循环也是将问题变得更小

1
2
3
4
5
6
7
8
9
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)复杂度问题

1
2
3
4
5
6
7
8
9
10
11
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
	}
}