空間復(fù)雜度：
根據(jù)算法寫成的程序在執(zhí)行時(shí)占用存儲(chǔ)單元的長度。這個(gè)長度往往與輸入數(shù)據(jù)的規(guī)模有關(guān)⌒魃蹋空間復(fù)雜度過高的算法可能導(dǎo)致使用的內(nèi)存超限，造成程序非正常中斷辅鲸。
我們要處理一個(gè)變量N格郁，如下面程序，要輸出0-N之間的所有整數(shù)独悴。
由于這是一個(gè)遞歸程序例书，加入N=100000，那么在程序結(jié)束之前要在存儲(chǔ)空間中存下所有1-100000的所有數(shù)據(jù)刻炒。如圖：
就是說內(nèi)存需要的空間隨著N做線性增長决采。所以空間復(fù)雜度可以用一個(gè)常數(shù)*N來表示。即：
時(shí)間復(fù)雜度：
根據(jù)算法寫成的程序在執(zhí)行時(shí)耗費(fèi)時(shí)間的長度坟奥。這個(gè)長度往往與輸入數(shù)據(jù)的規(guī)模有關(guān)树瞭。時(shí)間復(fù)雜度過高的算法可能導(dǎo)致我們?cè)谟猩甓嫉炔坏竭\(yùn)行的結(jié)果。
數(shù)據(jù)運(yùn)算主要是做加減乘除四則運(yùn)算爱谁，而計(jì)算機(jī)做加減法的速率比乘除法要快的多晒喷，加減法可以忽略不計(jì)，所以時(shí)間復(fù)雜度主要是看程序做了多少次乘除法運(yùn)算访敌。
比如上面是一個(gè)多項(xiàng)式的運(yùn)算的程序凉敲，主要的運(yùn)算都是在for循環(huán)里面做的，pow(x,i)求的是x的i次方捐顷，所以做了i-1次乘法，再加上最前面乘以a[i]的一次雨效，每一個(gè)for循環(huán)里面做了i次乘法迅涮，一共n次循環(huán)，所以一共做了次乘法徽龟。用時(shí)間復(fù)雜度表示為：
第二個(gè)程序是求同一個(gè)多項(xiàng)式運(yùn)算的程序叮姑，這個(gè)程序里面每次for循環(huán)只做了一次乘法，所以一共做了n次乘法据悔。用時(shí)間復(fù)雜度表示為
比較上面兩個(gè)程序传透，雖然不知道C1,C2和C分別為多少，但是當(dāng)n足夠大時(shí)极颓，n2遠(yuǎn)遠(yuǎn)大于n朱盐，所以這個(gè)時(shí)候第一個(gè)程序的時(shí)間復(fù)雜度要大于第二個(gè)程序的時(shí)間復(fù)雜度！
復(fù)雜度的漸進(jìn)表示法：
????????當(dāng)我們?cè)诜治鏊惴◤?fù)雜度的時(shí)候菠隆，其實(shí)是沒有必要分析這個(gè)算法把什么操作做了多少次的兵琳，我們只需要知道隨著處理數(shù)據(jù)規(guī)模的增大窍箍，這個(gè)復(fù)雜度增長的性質(zhì)會(huì)怎么樣就足夠了向臀。比如說比較前面兩個(gè)算法的時(shí)候，我們只要知道當(dāng)n足夠大的時(shí)候，T1是n2在起主要作用巨朦，T2是n在起主要作用，所以在n足夠大的時(shí)候T1肯定比T2大就可以了玩徊。
? ? ? ? 所以就有了復(fù)雜度的漸進(jìn)表示法：
????????我們?nèi)绻岩粋€(gè)時(shí)間復(fù)雜度T(n)寫成是一個(gè)O(f(n))的形式谍失，即表示存在常數(shù)C>0，
>0使得當(dāng)
的時(shí)候嫡丙，f(n)大概表現(xiàn)的是T(n)的一個(gè)上界拴袭，即
。簡單表示來說對(duì)于充分大的n而言迄沫，O(f(n))表示f(n)是T(n)的某種上界稻扬。
????????類似的，如果是一個(gè)的形式羊瘩，表示存在常數(shù)C>0泰佳，
>0使得當(dāng)
的時(shí)候，g(n)就是T(n)的某種下界尘吗，即
逝她。
????????如果是的形式，那就表示對(duì)于這個(gè)
里面的函數(shù)來說睬捶，O和Ω是同時(shí)成立的黔宛，它既是上界也是下界。即同時(shí)有
和
擒贸。
上面關(guān)于時(shí)間復(fù)雜度的漸進(jìn)表示法同樣適用于空間復(fù)雜度臀晃。但是我們要注意到一個(gè)函數(shù)的上界和下界并不是唯一的，比如一個(gè)算法的復(fù)雜度是n的常數(shù)倍介劫，那么我們既可以把它寫成O(n)徽惋，也可以寫成O(n2)，還可以寫成O(n3)...下界也是一樣座韵。但是太大的上界和太小的下界對(duì)于分析算法的效率而言是沒有什么幫助的险绘。我們?cè)诜治鏊惴ㄐ实臅r(shí)候希望它的上界和下界和真實(shí)情況越貼近越好，所以我們一般在寫的時(shí)候通常寫的是我們能力范圍內(nèi)找到的最小的上界和最大的下界誉碴。
下面三張圖分別為不同函數(shù)的增長速度數(shù)值表宦棺、不同函數(shù)增長速度線形圖和每秒10億指令計(jì)算機(jī)的運(yùn)行時(shí)間表可供參考。
