這是《算法圖解》的第一篇讀書筆記，內(nèi)容關(guān)于表示算法復(fù)雜度的漸近表示法以及一個(gè)簡單但高效的算法：二分法。

1 .漸近表示法

1.1定義

算法的運(yùn)行需要時(shí)間，這就需要衡量算法運(yùn)行時(shí)間即時(shí)間復(fù)雜度的方式。這個(gè)衡量方式就被成為漸近表示法（大O表示法）。
漸近表示法用于描述算法在最糟糕情況下的運(yùn)行時(shí)間，同時(shí)也表示了算法運(yùn)行時(shí)間隨問題規(guī)模擴(kuò)大而增長的幅度。

1.2如何使用漸近表示法確定時(shí)間復(fù)雜度

一般而言，算法復(fù)雜度可用一個(gè)函數(shù)進(jìn)行表示。之后，僅保留函數(shù)中增長幅度最大的一項(xiàng)，而這一項(xiàng)就可用于衡量該算法的時(shí)間復(fù)雜度。

1.3時(shí)間復(fù)雜度的優(yōu)先級(jí)

以下為常見的漸近表示方式及復(fù)雜度的優(yōu)先級(jí)。其中，時(shí)間復(fù)雜度由上往下逐漸增加。

θ(1)：常數(shù)級(jí)
θ(log(n))：對(duì)數(shù)級(jí)
θ(n)：線性級(jí)
θ(nlog(n))：對(duì)數(shù)線性級(jí)
θ(n^2)：平方級(jí)
θ(n^3)：立方級(jí)
O(n^k)：多項(xiàng)式級(jí)
?(k^n)：指數(shù)級(jí)
θ(n!)：階乘級(jí)

2.二分法

2.1定義

二分法指的是在求解問題的過程中不斷地折半縮減問題規(guī)模，最終在有限時(shí)間(log2 n)內(nèi)求出問題答案的算法。

2.2實(shí)例

使用二分法的案例有很多，下面演示如何用二分法近似求出sqrt(2)，精度在0.00000001

#二分法近似求出sqrt(2)，精度在0.00000001
import math

def dichotomy(target,precision):
    square_target=int(target*target)
    low=0
    high=int(square_target**2)
    result=(low+high)/2
    while len(str(result))<10:
        if result**2<=square_target:
            low=result
        else:
            high=result
        result=(low+high)/2
    return result

print(dichotomy(math.sqrt(2),8))