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ù)雜度算法舉例

對分查找

問題

已知一串整數(shù)按順序排布，尋找某個(gè)指定數(shù)的下標(biāo)

求解

考慮已經(jīng)按順序排列，那么使用二分查找的方法即可。對于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
    }
}