一、算法的定義

• 算法這個單詞最早出現(xiàn)在波斯數(shù)學(xué)家阿勒·花刺子密在公元825年（相當(dāng)于中國的唐朝時期）所寫的《印度數(shù)字算術(shù)》中。

• 如今普遍認(rèn)可的對算法的定義是：算法是解決特定問題求解步驟的描述，在計算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。

二、算法的特性

• 五個基本特性
  • 輸入：具有零個或多個輸入
  • 輸出：至少有一個或多個輸出
  • 有窮性：指在算法在執(zhí)行有限的步驟后自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成
  • 確定性：每一步驟都具有確定的含義，不會出現(xiàn)二義性
  • 可行性：每一步都必須可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成

三、算法設(shè)計的要求

• 正確性
• 可讀性
• 健壯性
• 時間效率高和存儲量低

四、算法效率的度量方法

• 事后統(tǒng)計方法（不推薦）：通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機(jī)計時器對不同算法編制的程序的運(yùn)行時間進(jìn)行比較，從而確定算法效率的高低。但這種方法顯然是有很大的缺陷的：

  • 必須依據(jù)算法事先編制好程序，這通常需要花費(fèi)大量的時間和精力。如果編制出來發(fā)現(xiàn)它根本是很糟糕的算法，不是竹籃打水一場空嗎？
  • 時間的比較依賴計算機(jī)硬件和軟件等環(huán)境因素，有時會掩蓋算法本身的優(yōu)劣
  • 算法的測試數(shù)據(jù)設(shè)計困難，并且程序的運(yùn)行時間往往還與測試數(shù)據(jù)的規(guī)模有很大關(guān)系，效率高的算法在小的測試數(shù)據(jù)面前往往得不到體現(xiàn)。

• 事前分析估算方法（推薦）：在計算機(jī)程序編制前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算。經(jīng)過分析，一個用高級程序語言編寫的程序在計算機(jī)上運(yùn)行時所消耗的時間取決于下列因素：
  1.算法采用的策略、方法
  2.編譯產(chǎn)生的代碼質(zhì)量
  3.問題的輸入規(guī)模
  4.機(jī)器執(zhí)行指令的速度

  第1條當(dāng)然是算法好壞的根本，第2條要由軟件來支持，第4條要看硬件性能。也就是說，拋開這些與計算機(jī)硬件、軟件有關(guān)的因素，一個程序的運(yùn)行時間，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題輸入規(guī)模是指輸入量的多少。

最終，在分析程序的運(yùn)行時間時，最重要的是把程序看成是獨(dú)立于程序設(shè)計語言的算法或一系列步驟。

五、函數(shù)的漸進(jìn)增長

六、算法時間復(fù)雜度

• 定義：在進(jìn)行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間量度，記作：T(n) = O(f(n))。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。

• 這樣用大O()來體現(xiàn)算法時間復(fù)雜度的記法，我們稱之為大O記法。

  • 一般情況下，隨著n的增大，T(n)增長最慢的算法為最優(yōu)算法。

• 推導(dǎo)大O階方法
  1.用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)
  2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項
  3.如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)，得到的結(jié)果就是大O階。

• 常見的時間復(fù)雜度

  
  

七、最壞情況與平均情況

八、算法空間復(fù)雜度

九、結(jié)尾語

希望大家在今后的學(xué)習(xí)中，好好利用算法分析的工具，改進(jìn)自己的代碼，讓計算機(jī)輕松一點，這樣你就更加勝人一籌。

參考：《大話數(shù)據(jù)結(jié)構(gòu)》
程杰 著