算法：
算法是解決特定問題求解步驟的描述让腹，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作达布。
2.4 算法的定義
什么是算法呢？算法是描述解決問題的方法斩熊。
算法定義中往枣，提到了指令，指令能被人或機器等計算裝置執(zhí)行粉渠。它可以是計算機指令分冈，也可以是我們平時的語言文字。
為了解決某個或某類問題霸株，需要把指令表示成一定的操作序列雕沉，操作序列包括一組操作，每一個操作都完成特定的功能去件，這就是算法了坡椒。
2.5 算法的特性
算法具有5個基本特征：輸入，輸出尤溜，有窮性倔叼，確定性和可行性。
1 輸入輸出
算法具有零個或多個輸入宫莱。 算法至少有一個或多個輸出丈攒。
算法是一定需要輸出的，不需要輸出授霸，你用這個算法干嘛巡验？輸出的形式可以是打印輸出，也可以是返回一個或多個值等碘耳。
2 有窮性
有窮性：指算法在執(zhí)行有限的步驟之后显设，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成辛辨。
當(dāng)然這里有窮的概念并不是純數(shù)學(xué)意義的捕捂，而是在實際應(yīng)用當(dāng)中合理的，可以接受的“有邊界”愉阎。
3 確定性
確定性：算法的每一步驟都具有確定的含義绞蹦，不會出現(xiàn)二義性。
算法在一定條件下榜旦，只有一條執(zhí)行路徑幽七，相同的輸入只能有唯一的輸出結(jié)果。算法的每個步驟被精確定義而無歧義溅呢。
4 可行性
可行性：算法的每一步都必須是可行的澡屡，也就是說猿挚，每一步都能夠通過執(zhí)行有限次數(shù)完成。
可行性意味著算法可以轉(zhuǎn)換為程序上機運行驶鹉，并得到正確的結(jié)果绩蜻。
2.6 算法設(shè)計的要求
算法不是唯一的，同一個問題室埋，可以有多種解決問題的算法办绝。
2.6.1 正確性
正確性：算法的正確性是指算法至少應(yīng)該具有輸入，輸出和加工處理無歧義性姚淆，能正確反映問題的需求孕蝉，能夠得到問題的正確答案。
但是算法的“正確”通常在用法上有很大的區(qū)別腌逢，大體分為一下4個層次降淮。
- 1.算法程序沒有語法錯誤。
- 2.算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果搏讶。
- 3.算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果佳鳖。
- 4.算法程序?qū)τ诰倪x擇的，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果媒惕。
對于這4層含義系吩，層次1要求最低，但是僅僅沒有語法錯誤實在談不上是好算法妒蔚。而層次4是最困難的淑玫，我們幾乎不可能逐一驗證所有的輸入都得到正確的結(jié)果。
因此算法的正確性在大部分情況下都不可能用程序來證明面睛，而是用數(shù)學(xué)方法來證明的。證明一個復(fù)雜算法在所有層次上都是正確的尊搬，代價非常昂貴叁鉴。所以一般情況下，我們把層次3作為一個算法是否正確的標(biāo)準(zhǔn)佛寿。
2.6.2 可讀性
可讀性：算法設(shè)計的另一目的是為了便于閱讀幌墓，理解和交流。
我們寫代碼的目的冀泻，一方面是為了讓計算機執(zhí)行常侣，但還有一個重要的目的是為了便于他人閱讀，讓人理解或交流弹渔，自己將來也可能閱讀胳施，如果可讀性不好，時間長了自己都不知道寫了些什么肢专∥杷粒可讀性是算法好壞很重要的標(biāo)志焦辅。
2.6.3 健壯性
健壯性：當(dāng)輸入數(shù)據(jù)不合法時，算法也能做出相關(guān)處理椿胯，而不是產(chǎn)生異晨甑牵或莫名其妙的結(jié)果。
2.6.4 時間效率高和存儲量低
時間效率指的是算法的執(zhí)行時間哩盲。
存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間前方，主要指算法程序運行時所占用的內(nèi)存或外部硬盤存儲空間。
設(shè)計算法應(yīng)該盡量滿足時間效率高和存儲量低的需求廉油。
2.7 算法效率的度量方法
設(shè)計算法要提高效率惠险。這里效率大都指算法的執(zhí)行時間。
2.7.1 事后統(tǒng)計方法
事后統(tǒng)計方法：這種方法主要是通過設(shè)計好的測試程序和數(shù)據(jù)娱两，利用計算機計時器對對不同算法編制的程序的運行時間進(jìn)行比較莺匠，從而確定算法效率的高低。
缺陷：
- 必須依據(jù)算法事先編制好程序十兢，這通常需要花費大量的時間和精力趣竣。
- 時間的比較依賴計算機硬件和軟件等環(huán)境因素。
- 算法的測試數(shù)據(jù)設(shè)計困難旱物，并且程序的運行時間往往還與測試數(shù)據(jù)的規(guī)模有很大關(guān)系遥缕，效率高的算法在小的測試數(shù)據(jù)面前往往得不到體現(xiàn)。
基于事后統(tǒng)計方法有這樣那樣的缺陷宵呛，我們考慮不予采納单匣。
2.7.2 事前分析估算方法
事前分析估算方法：在計算機程序編制前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算宝穗。
一個程序的運行時間户秤，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題輸入規(guī)模是指輸入量的多少逮矛。
測定運行時間最可靠的方法就是計算對運行時間有消耗的基本操作的執(zhí)行次數(shù)鸡号。運行時間與這個計數(shù)成正比。
不記那些循環(huán)索引的遞增和循環(huán)終止條件须鼎，變量聲明鲸伴，打印結(jié)果等操作，最終晋控，在分析程序的運行時間時汞窗，最重要的是把程序看成是獨立于程序設(shè)計語言的算法或一系列步驟。
同樣問題的輸入規(guī)模是n,求和算法的第一種赡译，求1+2+3+4+...+n需要一段代碼執(zhí)行n次仲吏。那么這個問題的輸入規(guī)模使得操作數(shù)量是f(n)=n，顯然運行100次的同一段代碼規(guī)模試運行10次的10倍。而第二種蜘矢，無論n為多少狂男，運行次數(shù)都為1，即f(n)=1品腹，第三種岖食，運算100次是運算10次的100倍，因為他是f(n)=n2舞吭。
隨著n值的越來越大泡垃，它們在時間效率上的差異也就越來越大。
2.8 函數(shù)的漸進(jìn)增長
函數(shù)的漸進(jìn)增長：
給定兩個函數(shù)
f(n)和g(n),如果存在一個整數(shù)N羡鸥，使得對于所有的n>N,f(n)總是比g(n)大蔑穴，那么，我們說f(n)的增長漸近快于g(n)惧浴。
與最高次項相乘的常數(shù)并不重要存和。
最高次項的指數(shù)大的，函數(shù)隨著n的增長衷旅，結(jié)果也會變得增長特別快捐腿。
判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常呈炼ィ可以忽略茄袖，而更應(yīng)該關(guān)注主項(最高階項)的階數(shù)。
判斷一個算法好不好嘁锯，我們只通過少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的宪祥。
某個算法嘴拢，隨著n的增大蝗茁，它會越來越優(yōu)于另一算法，或者越來越差于另一算法统翩。
2.9 算法時間復(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)算法。
由此算法時間復(fù)雜度的定義可知顷编，我們的三個求和算法的時間復(fù)雜度分別為O(n),O(1),O(n2)戚炫。我們分別給它們?nèi)×朔枪俜降拿Q，O(1)叫常數(shù)階媳纬，O(n)叫線性階双肤，O(n2)叫平方階。
2.9.2 推導(dǎo)大O階方法
如何分析一個算法的時間復(fù)雜度呢钮惠？即如何推導(dǎo)大O階呢茅糜？
推導(dǎo)大O階：
- 用常數(shù)
1取代運行時間中的所有加法常數(shù)。- 在修改后的運行次數(shù)函數(shù)中素挽，只保留最高階項蔑赘。
- 如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)预明。得到的結(jié)果就是大O階缩赛。
2.9.3 常數(shù)階
這種與問題的大小無關(guān)(n的多少)，執(zhí)行時間恒定的算法贮庞，我們稱之為具有O(1)的時間復(fù)雜度峦筒，又叫常數(shù)階。
注意：不管這個常數(shù)是多少窗慎，我們都記作O(1)物喷，而不是O(3)，O(12)等其他任何數(shù)字遮斥，這是初學(xué)者常常犯的錯誤峦失。
對于分支結(jié)構(gòu)而言，無論是真還是假术吗，執(zhí)行的次數(shù)都是恒定的尉辑，不會隨著n的變大而發(fā)生變化，所以單存的分支結(jié)構(gòu)(不包含在分支結(jié)構(gòu)中)较屿，其時間復(fù)雜度也是O(1)隧魄。
2.9.4 線性階
線性階的循環(huán)結(jié)構(gòu)會復(fù)雜很多，要確定某個算法的階次隘蝎，我們常常需要確定某個特定語句或某個語句集運行的次數(shù)购啄。因此我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運行情況嘱么。
對數(shù)階
平方階
循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運行的次數(shù)狮含。
其實理解大O推導(dǎo)不算難，難的是對數(shù)列的一些相關(guān)運算，這更多的是考察你的數(shù)學(xué)知識和能力几迄。
2.10 常見的時間復(fù)雜度
2.11### 最壞情況和平均情況
最壞情況運行時間是一種保證蔚龙，那就是運行時間將不會再壞了。在應(yīng)用中映胁，這是一種最重要的需求木羹，通常，除非特被指定屿愚，我們提到的運行時間都是最壞情況的運行時間汇跨。
平均運行時間是所有情況中最有意義的，因為它是期望的運行時間妆距。
對算法的分析穷遂，一種方法是計算所有情況的平均值，這種時間復(fù)雜度的計算方法稱為平均時間復(fù)雜度娱据。另一種方法是計算最壞情況下的時間復(fù)雜度蚪黑，這種方法稱為最壞時間復(fù)雜度。一般在沒有特殊說明的情況下中剩，都是指最壞時間復(fù)雜度忌穿。
2.12 算法空間復(fù)雜度
算法的空間復(fù)雜度：通過計算算法所需的存儲空間實現(xiàn)，算法空間復(fù)雜度的計算公式記作：S(n) = O(f(n)),其中结啼，n為問題的規(guī)模掠剑，f(n)為語句關(guān)于n所占存儲空間的函數(shù)。
通常郊愧，我們都使用“時間復(fù)雜度”來指運行時間的需求朴译，使用“空間復(fù)雜度”指空間需求。當(dāng)不用限定詞地使用“復(fù)雜度”時属铁，通常都是指時間復(fù)雜度眠寿。
