算法定義
算法定義：算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作。
算法的特性
1.輸入和輸出
算法具有零個或多個輸入。算法至少有一個或多個輸出。
2.有窮性
有窮性：指算法在執行有限的步驟之後，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間内完成。
3.确定性
确定性：算法的每一步驟都具有确定的含義，不會出現二義性。
4.可行性
可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次數完成。
算法設計的要求
1.正确性
正确性：算法的正确性是指算法至少應該具有輸入、輸出和加工處理無歧義、能正确反映問題的需求、能夠得到問題的正确答案。
①算法程式沒有文法錯誤。
②算法程式對于合法的輸入資料能夠産出滿足要求的輸出結果。
③算法程式對于非法的輸入資料能夠得出滿足規格說明的結果。
④算法程式對于精心選擇的，甚至刁難的測試資料都有滿足要求的輸出結果。
2.可讀性
可讀性：算法設計的另一個目的是為了便于閱讀、了解和交流。
3.健壯性
健壯性：當輸入資料不合法時，算法也能做出相關處理，而不是産生異常或莫名其妙的結果。
4.時間效率高和存儲量低
設計算法應該盡量滿足時間效率高和存儲量低的需求。
算法效率的度量方法
1.事後統計方法
事後統計方法：這種方法主要是通過設計好的測試程式和資料，利用計算機計時器對不同算法編制的程式的運作時間進行比較，進而确定算法效率的高低。
這種方法顯然是有很大缺陷的：
①必須依據算法事先編制好程式，這通常需要花費大量的時間和精力。
②時間的比較依賴計算機硬體和軟體等環境因素，有時會掩蓋算法本身的優劣。
③算法的測試資料設計困難，并且程式的運作時間往往還與測試資料的規模有很大關系。效率高的算法在小的測試資料面前往往得不到展現。
2.事前分析估算方法
事前分析估算方法：在計算機程式編制前，依據統計方法對算法進行估算。
一個用進階程式語言編寫的程式在計算機上運作所消耗的時間決定于下列因素：
①算法采用的政策、方法。
②編譯産生的代碼品質。
③問題的輸入規模。
④機器執行指令的速度。
第①條當然是算法好壞的根本，第②條要由軟體來支援，第④條要看硬體的性能。也就是說，抛開這些與計算機硬體、軟體有關的因素，一個程式的運作時間，依賴于算法的好壞和問題的輸入規模。所謂問題輸入規模是指輸入量的多少。
下面是兩種求和算法：
算法好壞顯而易見。
,這個算法的執行時間随着n的增加也将遠遠多于前面兩個。
最終，在分析程式的運作時間時，最重要的是把程式看成是獨立于程式設計語言的算法或一些列步驟。
函數的漸進增長
函數的漸進增長：給定兩個函數f(n)和g(n)，如果存在一個整數N，使得對于所有的n>N，f(n)總是比g(n)大，那麼，我們說f(n)的增長漸進快于g(n)。
①我們可以忽略加法常數。
②與最高次項相乘的常數并不重要。
③最高次項的指數大的，函數随着n的增長，結果也會增長的特别快。
判斷一個算法的效率時，函數中的常數和其他次要的項常常可以忽略，而更應該關注主項（最高階項）的階數。基本就可以分析出：某個算法，随着n的增大，它會越來越優于另一個算法，或者越來越差與另一個算法。
算法時間複雜度
算法時間複雜度定義
在進行算法分析時，語句總的執行次數T(n)是關于問題規模n的函數，進而分析T(n)随n的變化情況并确定T(n)的數量級。算法的時間複雜度，也就是算法的時間量度，記作：T(n)=O(f(n))。它表示随問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。
這樣用大寫O()來展現算法時間複雜度的記法，我們稱之為大O記法。
推導大O階方法
①用常數1取代運作時間中的所有加法常數。
②在修改後的運作次數函數中，隻保留最高階項。
③如果最高階項存在且不是1，則去除與這個項相乘的常數。
得到的結果就是大O階。
常數階
這個算法的運作次數函數是f(n)=3。根據推導大O階方法，第一步就是把常數項3改為1。沒有最高項，是以這個算法的時間複雜度為O(1)。
線性階
分析算法的複雜度，關鍵就是要分析循環結構的運作情況。
它的循環的複雜度為O(n)，因為循環體中的代碼要執行n次。
對數階
由
得到
。是以這個循環的時間複雜度為O(
) 。
平方階
時間複雜度O(
) 。
下面這個
時間複雜度O(
) 。
看這個
執行總次數是：
根據推導大O階方法，最終為O(
)。
了解大O推導不算難，難的是對數列的一些相關運算，這更多得是考察你的數學知識和能力。
常用的時間複雜度所消耗的時間從小到大依次是：
O(1)<O(
)<O(n)<O(
)<O(
)<O(
)<O(
)<O(n!)<O(
)
常數階<對數階<線性階<
階<平方階<立方階<指數階<O(n!)<O(
)
最壞情況與平均情況
最壞情況運作時間是一種保證，那就是運作時間将不會再壞了。在應用中，這是一種最重要的需求，通常，除非特别指定，我們提到的運作時間都是最壞情況的運作時間。
平均運作時間是所有情況中最有意義的，因為它是期望的運作時間。
一般在沒有特殊說明的情況下，都是指最壞時間複雜度。