1堵腹、時間復雜度

• 時間頻度
  一個算法執(zhí)行所耗費的時間尽棕，從理論上是不能算出來的地啰，必須上機運行測試才能知道莹菱。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多梧田，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多愿汰，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度乐纸。記為T(n)衬廷。

• 時間復雜度
  在剛才提到的時間頻度中，n稱為問題的規(guī)模汽绢，當n不斷變化時吗跋，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律宁昭。為此跌宛，我們引入時間復雜度概念。 一般情況下积仗，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)疆拘，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時寂曹，T(n)/f(n)的極限值為不等于零的常數(shù)哎迄，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度隆圆，簡稱時間復雜度漱挚。在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)渺氧，則時間復雜度為O(1),另外旨涝，在時間頻度不相同時，時間復雜度有可能相同侣背，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同白华，但時間復雜度相同哩治，都為O(n2)。 按數(shù)量級遞增排列衬鱼，常見的時間復雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)业筏，立方階O(n3),...， k次方階O(nk),指數(shù)階O(2n)鸟赫。隨著問題規(guī)模n的不斷增大蒜胖，上述時間復雜度不斷增大，算法的執(zhí)行效率越低抛蚤。 2台谢、空間復雜度 與時間復雜度類似，空間復雜度是指算法在計算機內執(zhí)行時所需存儲空間的度量岁经。記作: S(n)=O(f(n))我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規(guī)模朋沮。討論方法與時間復雜度類似，不再贅述缀壤。

• 漸進時間復雜度評價算法時間性能
  主要用算法時間復雜度的數(shù)量級(即算法的漸近時間復雜度)評價一個算法的時間性能樊拓。

2、類似于時間復雜度的討論

一個算法的空間復雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間塘慕，它也是問題規(guī)模n的函數(shù)筋夏。漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度图呢。一個算法在計算機存儲器上所占用的存儲空間条篷，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面蛤织。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的赴叹，是通過參數(shù)表由調用函數(shù)傳遞而來的，它不隨本算法的不同而改變指蚜。存儲算法本身所占用的存儲空間與算法書寫的長短成正比乞巧，要壓縮這方面的存儲空間，就必須編寫出較短的算法姚炕。算法在運行過程中臨時占用的存儲空間隨算法的不同而異摊欠，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變柱宦，我們稱這種算法是“就地"進行的些椒，是節(jié)省存儲的算法，如這一節(jié)介紹過的幾個算法都是如此掸刊；有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關免糕，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元石窑，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況牌芋。

如當一個算法的空間復雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時松逊，可表示為O(1)躺屁；當一個算法的空間復雜度與以2為底的n的對數(shù)成正比時，可表示為0(10g2n)经宏；當一個算法的空I司復雜度與n成線性比例關系時犀暑，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間烁兰，即一個機器字長空間耐亏；若形參為引用方式，則也只需要為其分配存儲一個地址的空間沪斟，用它來存儲對應實參變量的地址广辰，以便由系統(tǒng)自動引用實參變量。