> 一次數學課上，老師讓學生練習算數。于是讓他們一個小時內算出1+2+3+4+5+6+……+100的得數。全班只有高斯用了不到20分鐘給出了答案，因為他想到了用（1+100）+（2+99）+（3+98）……+（50+51）…………一共有50個101，所以50×101就是1加到一百的得數。后來人們把這種簡便算法稱作高斯算法。 ### 算法定義：一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序列 ### 算法的描述： 自然語言 流程圖 程序設計語言 偽碼 ### 算法的特性： - 輸入:有0個或多個輸入 - 輸出 : 有一個或多個輸出（處理結果） - 有窮性 : 算法應在執行有窮步后結束 - 確定性 : 每步定義都是確切、無歧義的 - 可行性 :算法中所有的操作都必須可以通過已經實現的基本操作執行有限次來實現。 ### 算法的評價 - 正確性 - 可讀性 - 健壯性 - 高效性（時間代價和空間代價） ### 算法的效率的度量 算法效率：用依據該算法編制的程序在計算機上執行所消耗的時間來度量 *事后統計 *事前分析估計 ~~~ 事后統計：利用計算機內的計時功能，不同算法的程序可以用一組或多組相同的統計數據，來分辨出優略。 缺點： 1.必須先運行依據算法編制的程序 2.所得時間統計量依賴于硬件、軟件等環境因素，掩蓋算法本身的優劣 2.事前分析估計： ~~~ 一個高級語言程序在計算機上運行所消耗的時間取決于： - 1.依據的算法選用何種策略 - 2.問題的規模 - 3.程序語言 - 4.編譯程序所產生機器代碼質量 - 5機器執行指令速度 注意：同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，——-使用絕對時間單位衡量算法效率不合適 ### 算法的時間和空間復雜性 ##### 時間復雜度（Time Complexity） 設算法中所有語句的語句頻度為t(n),f(n)是當n趨向無窮大時與t(n)為同階無窮大，則 算法的時間復雜度T(n)=O(f(n)) 其中：n為算法計算量或成為規模（size）; f(n)是運算時間隨n增大時的增長率； O(f(n))是算法時間特性的量度。 算法分析主要從 分析算法的時間復雜度、空間復雜度這兩個方面以考察算法的時間和空間效率。一般情況下，鑒于運算空間較為充足，故作算法的時間復雜度作為分析的重點。算法執行時間T(n)的數量級稱為算法的漸近時間復雜度，T(n)=O(f(n)),它表示隨著問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，簡稱時間復雜度。  ~~~ i=1; ① while (i<=n) i=i*2; ② 解： 語句1的頻度是1, 設語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log2n 取最大值f(n)=log2n, T(n)=O(log2n ) ~~~ 常見的時間復雜度按照數量級遞增排序依次為：常數階O(1)、對數階O(log2 n)、線性階O(n)、線性對數階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、K次方階O(n^k)、指數階O(2^n)。 > 愚公移山固然可敬，但發明推土機和炸藥，更加實在和聰明。希望大家在今后的學習中，好好利用算法分析的工具，改進自己的代碼，讓計算機輕松一點，這樣你就能更勝一籌.