#### 算法效率衡量 ##### **執行時間反應算法效率** 對于同一問題，我們給出了兩種解決算法，在兩種算法的實現中，我們對程序執行的時間進行了測算，發現兩段程序執行的時間相差懸殊（214.583347秒相比于0.182897秒），由此我們可以得出結論：**實現算法程序的執行時間可以反應出算法的效率，即算法的優劣。** * * * * * ##### **單靠時間值絕對可信嗎?**** 假設我們將第二次嘗試的算法程序運行在一臺配置古老性能低下的計算機中，情況會如何？很可能運行的時間并不會比在我們的電腦中運行算法一的214.583347秒快多少。 **單純依靠運行的時間來比較算法的優劣并不一定是客觀準確的！** 程序的運行離不開計算機環境（包括硬件和操作系統），這些客觀原因會影響程序運行的速度并反應在程序的執行時間上。那么如何才能客觀的評判一個算法的優劣呢？ * * * * * ##### **時間復雜度與“大O記法”** 我們假定計算機執行算法每一個基本操作的時間是固定的一個時間單位，那么有多少個基本操作就代表會花費多少時間單位。算然對于不同的機器環境而言，確切的單位時間是不同的，但是對于算法進行多少個基本操作（即花費多少時間單位）在規模數量級上卻是相同的，由此可以忽略機器環境的影響而客觀的反應算法的時間效率。 對于算法的時間效率，我們可以用“大O記法”來表示。 “**大O記法”：對于單調的整數函數f，如果存在一個整數函數g和實常數c>0，使得對于充分大的n總有f(n)<=c*g(n)，就說函數g是f的一個漸近函數（忽略常數），記為f(n)=O(g(n))。也就是說，在趨向無窮的極限意義下，函數f的增長速度受到函數g的約束，亦即函數f與函數g的特征相似。 時間復雜度：假設存在函數g，使得算法A處理規模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間復雜度，簡稱時間復雜度，記為T(n)** * * * * * ##### **如何理解“大O記法”** 對于算法進行特別具體的細致分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數量的規模函數中那些常量因子可以忽略不計。例如，可以認為3n2和100n2屬于同一個量級，如果兩個算法處理同樣規模實例的代價分別為這兩個函數，就認為它們的效率“差不多”，都為n2級。 * * * * * ##### **最壞時間復雜度** 分析算法時，存在幾種可能的考慮： * 算法完成工作最少需要多少基本操作，即**最優時間復雜度** * 算法完成工作最多需要多少基本操作，即**最壞時間復雜度** * 算法完成工作平均需要多少基本操作，即**平均時間復雜度** 對于最優時間復雜度，其價值不大，因為它沒有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價值。 對于最壞時間復雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。 對于平均時間復雜度，是對算法的一個全面評價，因此它完整全面的反映了這個算法的性質。但另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作內完成。而且，對于平均情況的計算，也會因為應用算法的實例分布可能并不均勻而難以計算。 **因此，主要關注算法的最壞情況，亦即最壞時間復雜度。** * * * * * ##### **時間復雜度的幾條基本計算規則** 1. 基本操作，即只有常數項，認為其時間復雜度為O(1) 2. 順序結構，時間復雜度按加法進行計算 3. 循環結構，時間復雜度按乘法進行計算 4. 分支結構，時間復雜度取最大值 5. 判斷一個算法的效率時，往往只需要關注操作數量的最高次項，其它次要項和常數項可以忽略 6. 在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度