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
    }
}