logN复杂度估算
logN复杂度的算法可以认为具有以下特性:
用常数时间将问题的大小削减为某一部分(通常是1/2)
例如分治法求最大子串问题,将一个$O(N^{2})$的问题削减为每个的1/2,每个问题复杂度为$O(N)$(有循环),所以该算法的复杂度估计为$O(NlogN)$
logN复杂度算法举例
对分查找
问题
已知一串整数按顺序排布,寻找某个指定数的下标
求解
考虑已经按顺序排列,那么使用二分查找的方法即可。对于For循环内部算法的复杂度是O(1),且每次循环都将问题缩小一半,所以认为这是一个O(logN)的算法
1 | func binary_search(data []int, target int) int { |
欧几里德算法
欧几里得算法是用于取最大公因数的算法(中国古代类似的算法好像是碾转相除法?)。这个算法中,每次循环也是将问题变得更小
1 | func gcd(a, b int) int { |
递归求幂
类似于二分查找,递归求幂的原理是$x^{2n} = x^{n} * x^{n}$相比于普通阶乘,减少了乘法的次数。同时,也是每次循环问题(N)减为原来的一半,也是一个O(logN)复杂度问题
1 | func pow(x, n int) int { |