第二章 算法
算法的定義：算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作朗若。
算法具有5個基本特性：輸入，輸出昌罩，有窮性哭懈，確定性和可行性。
輸入輸出：算法劇透零個或多個輸入茎用，至少一個輸出遣总。
有窮性：指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)轨功，并且每一個步驟在可接受的時間內(nèi)完成旭斥。
確定性：算法的每一步都具有確定的含義，不會出現(xiàn)二義性古涧。
可行性：算法的每一步都是可行的垂券，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成羡滑。
一個好的算法應該具備正確性菇爪，可讀性，健壯性柒昏，高效率和低存儲量的特點凳宙。
算法效率的度量方法：事后統(tǒng)計方法和事前分析估算法；
事后統(tǒng)計法：通過設計好的測試程序和數(shù)據(jù)职祷，利用計算機計時器對不同算法編制的程序的運行時間進行比較氏涩，從而確定算法效率的高低。
事前分析估算法：在程序編制前有梆，依據(jù)統(tǒng)計方法對算法進行估算是尖。
一個程序的運行時間，依賴于算法的好壞和問題的輸入規(guī)模泥耀。所謂問題輸入規(guī)模是指輸入量的多少饺汹。
測定算法運行時間最可靠的方法就是計算對運行時間有消耗的基本操作的執(zhí)行次數(shù)，運行時間與這個計數(shù)成正比爆袍。
函數(shù)的漸進增長：給定兩個函數(shù)f(n)和g(n),如果存在一個整數(shù)N首繁，使得對于所有的n>N,f(n)總是比g(n)大，那么我們說f(n)的增長漸進大于g(n)陨囊。
判斷一個算法的效率時弦疮，函數(shù)中的常數(shù)和其他次要項常常可以忽略蜘醋，而更應該關(guān)注主項（最高階項）的階數(shù)胁塞。
上面這組數(shù)據(jù)可以看出，當n的值越來越大压语，會發(fā)現(xiàn)啸罢，3n+1已經(jīng)沒法和2n^2的結(jié)果相比較，最終幾乎可以忽略不計胎食。同時隨著n的值變得非常大之后扰才，算法G 已經(jīng)非常趨近于算法I了。
算法時間復雜度：在進行算法分析時厕怜，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)衩匣，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復雜度也就是算法的時間量度粥航，記作T(n)=O(f(n))琅捏。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同递雀，稱作算法的漸進時間復雜度柄延，簡稱為時間復雜度。其中f(n)是問題規(guī)模n的某個函數(shù)缀程。
這樣用大寫O()來體現(xiàn)算法時間復雜度的記法搜吧，我們稱之為大O記法。
一般情況下杠输，隨著n的增大赎败，T(n)增長最慢的算法為最優(yōu)算法。
O(1)-常數(shù)階
O(n)-線性階
O(n^2)-平方階
推導大O階方法：
1.用常數(shù)1取代運行時間中所有的加法常數(shù)蠢甲；
2.在修改后的運行次數(shù)函數(shù)中僵刮，只保留最高階項；
3.如果最高階項存在且不是1鹦牛，則去除與這個項相乘的常數(shù)搞糕；
得到的結(jié)果就是大O階。
分析算法的時間復雜度關(guān)鍵就是分析循環(huán)結(jié)構(gòu)的運行情況曼追。
常見的時間復雜度：
最壞情況運行時間是一種保證窍仰，那就是運行時間不會再壞了。在應用中礼殊，這是一種最重要的需求驹吮，通常针史，除非特別指定，我們提到的運行時間都是最壞情況運行時間碟狞。
平均運行時間是所有情況中最有意義的啄枕，因為它是期望的運行時間。
算法的空間復雜度通過計算算法所需的存儲空間實現(xiàn)族沃，公式記作：S(n)=O(f(n))频祝，其中，n為問題的規(guī)模脆淹，f(n)為語句關(guān)于n所占存儲空間的函數(shù)常空。
