空間復雜度：
根據(jù)算法寫成的程序在執(zhí)行時占用存儲單元的長度。這個長度往往與輸入數(shù)據(jù)的規(guī)模有關?？臻g復雜度過高的算法可能導致使用的內存超限，造成程序非正常中斷。
我們要處理一個變量N，如下面程序，要輸出0-N之間的所有整數(shù)。
由于這是一個遞歸程序，加入N=100000，那么在程序結束之前要在存儲空間中存下所有1-100000的所有數(shù)據(jù)。如圖：
就是說內存需要的空間隨著N做線性增長。所以空間復雜度可以用一個常數(shù)*N來表示。即：
時間復雜度：
根據(jù)算法寫成的程序在執(zhí)行時耗費時間的長度。這個長度往往與輸入數(shù)據(jù)的規(guī)模有關。時間復雜度過高的算法可能導致我們在有生之年都等不到運行的結果。
數(shù)據(jù)運算主要是做加減乘除四則運算，而計算機做加減法的速率比乘除法要快的多，加減法可以忽略不計，所以時間復雜度主要是看程序做了多少次乘除法運算。
比如上面是一個多項式的運算的程序，主要的運算都是在for循環(huán)里面做的，pow(x,i)求的是x的i次方，所以做了i-1次乘法，再加上最前面乘以a[i]的一次，每一個for循環(huán)里面做了i次乘法，一共n次循環(huán)，所以一共做了次乘法。用時間復雜度表示為：
第二個程序是求同一個多項式運算的程序，這個程序里面每次for循環(huán)只做了一次乘法，所以一共做了n次乘法。用時間復雜度表示為
比較上面兩個程序，雖然不知道C1,C2和C分別為多少，但是當n足夠大時，n2遠遠大于n，所以這個時候第一個程序的時間復雜度要大于第二個程序的時間復雜度！
復雜度的漸進表示法：
????????當我們在分析算法復雜度的時候，其實是沒有必要分析這個算法把什么操作做了多少次的，我們只需要知道隨著處理數(shù)據(jù)規(guī)模的增大，這個復雜度增長的性質會怎么樣就足夠了。比如說比較前面兩個算法的時候，我們只要知道當n足夠大的時候，T1是n2在起主要作用，T2是n在起主要作用，所以在n足夠大的時候T1肯定比T2大就可以了。
? ? ? ? 所以就有了復雜度的漸進表示法：
????????我們如果把一個時間復雜度T(n)寫成是一個O(f(n))的形式，即表示存在常數(shù)C>0，
>0使得當
的時候，f(n)大概表現(xiàn)的是T(n)的一個上界，即
。簡單表示來說對于充分大的n而言，O(f(n))表示f(n)是T(n)的某種上界。
????????類似的，如果是一個的形式，表示存在常數(shù)C>0，
>0使得當
的時候，g(n)就是T(n)的某種下界，即
。
????????如果是的形式，那就表示對于這個
里面的函數(shù)來說，O和Ω是同時成立的，它既是上界也是下界。即同時有
和
。
上面關于時間復雜度的漸進表示法同樣適用于空間復雜度。但是我們要注意到一個函數(shù)的上界和下界并不是唯一的，比如一個算法的復雜度是n的常數(shù)倍，那么我們既可以把它寫成O(n)，也可以寫成O(n2)，還可以寫成O(n3)...下界也是一樣。但是太大的上界和太小的下界對于分析算法的效率而言是沒有什么幫助的。我們在分析算法效率的時候希望它的上界和下界和真實情況越貼近越好，所以我們一般在寫的時候通常寫的是我們能力范圍內找到的最小的上界和最大的下界。
下面三張圖分別為不同函數(shù)的增長速度數(shù)值表、不同函數(shù)增長速度線形圖和每秒10億指令計算機的運行時間表可供參考。
