時間複雜度（算法分析）

算法分析

在現在這個資訊爆炸的時代，處理資料的量也越來越大。是以人們在用計算機來解決日常生活生産的問題的時候難免會有這樣的疑問。

我的程式會運作多長時間？

我的程式會耗多少的記憶體？

這次我們就來簡單讨論一下第一個“我的程式會運作多長時間？”。

運作時間

要知道一個程式的運作時間，最簡單的方法就是計時啦，簡單粗暴。

但是這自然要問，我不可能每一次都用個秒表去測量吧，而且程式的運作時間會受到多種因素的幹擾（作業系統，計算機的性能參數等等），是以就算用秒表測量得出的數值也不具有什麼意義。

是以自然我們要用一種相對的測量方法，我們可以通過計算一個對象被操作的次數來計算程式相對的運作時間。

下面我們分析一個簡單的例子，看看怎樣來估計程式的運作時間

public int sum(int[] a,int[] b){
    int sum=;
    for(int i =; i<a.length; i++){
        for(int j=; j<b.length; j++){
            sum=sum+a[i]+b[j];
        }
    }
    return sum;
}
           

分析上面的求和代碼，我們可以看到a中的每一個元素與每一個b中的元素求和，假設數組的長度（a.length）比較大，而且兩數組長度近似相等（n=a.length=b.length）。那麼明顯每個數組被通路的次數為 n2 ，兩個數組就是 2n2 。現在我們假定運作時間就是輸入資料的規模大小（n）的函數： T(n)=2n2 。而且事實也的确是這樣。

也可以用大O記法，記作 O(n2) （通常忽略低階項和常數項），叫作時間複雜度。

這樣就給出了一個我們估計程式運作時間的相對參考量，雖然并不能非常準确的計算程式的運作時間。但是至少也給出來程式的運作時間和輸入資料的規模的函數變化規律。就像上面的例子運作時間跟輸入資料的規模成平方增長。

常用算法的時間複雜度

上圖取自維基百科，上面列出了常用的算法的時間複雜度清單。

數學定義

在最後給出算法分析的數學基礎，數學定義。

大O記号

O(g(n))={ f(n): 存在正常數c和n0，使所有n>n0，有0≦f(n)≦c*g(n)}

上面的定義說明了O(g(n))是一個函數集合，集合裡面的函數滿足g(n)的常數倍是函數f(n)的一個上界，即f(n)有上界。

Ω記号

Ω(g(n))={ f(n):存在正常數c和n0，使所有n>n0，有0≦ c*g(n)≦f(n)}

上面的定義說明集合裡面的函數滿足g(n)的常數倍是函數f(n)的一個下界，即f(n)有下界。

Θ記号

Θ(g(n))，當且僅的，f(n)屬于O(g(n))和Ω(g(n))。

可見Θ是更強的形式。Θ蘊含大O和Ω。

有了這個數學基礎後就可以證明當分析程式的成本的時候，大多時候可以忽略掉低次項和常數相。

總結

當然算法是一門很大的學科，絕不僅隻有這些内容。如果各位同學有興趣可以看一下相關的教材。