一蚓峦、數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系
數(shù)據(jù)結(jié)構(gòu)與算法是相互依賴舌剂，不可分割的。
本書所談及的算法枫匾，為了更好地理解好數(shù)據(jù)結(jié)構(gòu)架诞，并不會(huì)詳細(xì)談及算法的方方面面拟淮。
二干茉、算法的定義
算法，通俗地講很泊，是描述解決問(wèn)題的方法角虫。
如今普遍認(rèn)可的算法定義是：
?算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列委造，并且每條指令表示一個(gè)或多個(gè)操作戳鹅。
對(duì)于特定的問(wèn)題，是可以有多種算法來(lái)解決的昏兆。
三枫虏、算法的特性
? ? 算法有五個(gè)基本特性：輸入、輸出爬虱、有窮性隶债、確定性和可行性。
1跑筝、輸入：算法有零個(gè)或多個(gè)輸入死讹。
2、輸出：算法至少有一個(gè)或多個(gè)輸出曲梗。
3赞警、有窮性：指算法在執(zhí)行有限步驟之后妓忍，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成愧旦。
4世剖、確定性：算法的每一個(gè)步驟都具有確定的含義，不會(huì)出現(xiàn)二義性忘瓦。
5搁廓、可行性：算法的每一步都是可行的，即耕皮，每一步都能通過(guò)執(zhí)行有限次數(shù)完成境蜕。
四、算法設(shè)計(jì)的要求
? ?上面算法的特性凌停，是用來(lái)判斷是不是算法粱年？再進(jìn)一步，一個(gè)問(wèn)題罚拟，有多種解決方式台诗，即可能有多種解決方法，那我們?cè)趺磁袛嘁粋€(gè)算法是不是一個(gè)好算法赐俗，這就要涉及到算法設(shè)計(jì)的要求拉队。
1、正確性：算法的正確性是指算法至少應(yīng)該具有正確輸入阻逮、輸出和加工處理無(wú)歧義性粱快、能正確反映問(wèn)題的需求、能夠得到問(wèn)題的正確答案叔扼。
2事哭、可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流瓜富。
3鳍咱、健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)的處理与柑，而不是產(chǎn)生異嘲迹或莫名其妙的結(jié)果。
4价捧、時(shí)間效率高和存儲(chǔ)量低：好的算法還應(yīng)該具有時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)丑念。
? 綜上，好的算法干旧，應(yīng)該具有正確性渠欺、可讀性、健壯性椎眯、高效率和低存儲(chǔ)量的特點(diǎn)挠将。
五胳岂、算法效率的度量
我們已經(jīng)知道了一個(gè)好的算法應(yīng)該具有的特征。剛才我們提到設(shè)計(jì)算法要提高效率舔稀，這里的效率指算法的運(yùn)行時(shí)間乳丰，那我們?nèi)绾味攘恳粋€(gè)算法的運(yùn)行時(shí)間呢？
????? ? 度量運(yùn)行時(shí)間内贮，主要有兩類方法产园，事后統(tǒng)計(jì)法和事前分析估算法；事后統(tǒng)計(jì)方法夜郁，主要是通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)什燕，利用計(jì)算機(jī)編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低竞端∈杭矗基于事后統(tǒng)計(jì)方法有不科學(xué)、不準(zhǔn)確的缺點(diǎn)事富，考慮不予采納技俐，現(xiàn)在更多地是考慮事前分析估算方法 。
????????事前分析估算方法统台，即在編程之前雕擂，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。
拋開(kāi)與硬件贱勃、軟件有關(guān)的因素井赌，一個(gè)程序的運(yùn)行時(shí)間，依賴于算法的好壞和問(wèn)題的輸入規(guī)模募寨。所謂問(wèn)題的輸入規(guī)模是指輸入量的多少族展。
由計(jì)算1到100的和的兩個(gè)算法可以看出森缠，測(cè)定運(yùn)行時(shí)間最可靠的方法是計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本步驟的執(zhí)行次數(shù)拔鹰。
不關(guān)心編寫程序用什么語(yǔ)言，在分析程序的運(yùn)行時(shí)間時(shí)贵涵，最重要的是把程序看成是獨(dú)立于程序設(shè)計(jì)語(yǔ)言的算法或一系列步驟列肢。
?在分析一個(gè)算法時(shí)間時(shí)，重要的是把基本操作的數(shù)量與輸入規(guī)模并聯(lián)起來(lái)宾茂，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)瓷马。把基本操作的數(shù)量和輸入規(guī)模并聯(lián)起來(lái)，最直接有效的方式是畫出兩者的函數(shù)圖跨晴。
六欧聘、函數(shù)的漸進(jìn)增長(zhǎng)
?有時(shí)候通過(guò)計(jì)算算法的基本操作的數(shù)量和輸入規(guī)模，然后作出圖端盆，比較繁瑣怀骤。有沒(méi)有更簡(jiǎn)便的方式呢费封？
函數(shù)的漸近增長(zhǎng)，是遞增函數(shù)的一種特性蒋伦，其定義為：
??? ? 函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)弓摘，如果存在一個(gè)整數(shù)N，使得所有的n>N,f(n)總是比g(n)大痕届，那么韧献，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)。
判斷一個(gè)函數(shù)的漸近增長(zhǎng)特性研叫，即判斷一個(gè)算法的效率時(shí)锤窑，函數(shù)中的常數(shù)和其他的次要項(xiàng)可以忽略，要關(guān)注主項(xiàng)（最高階項(xiàng)）嚷炉。
??????我們發(fā)現(xiàn)果复，如果我們可以對(duì)比這幾個(gè)算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸近增長(zhǎng)性，基本就可以分析出：某個(gè)算法渤昌，隨著n的增大虽抄，它會(huì)越來(lái)越優(yōu)于另一個(gè)算法，或者越來(lái)越差于某個(gè)算法独柑。這其實(shí)是事前估算方法的理論依據(jù)迈窟。
七、算法的時(shí)間復(fù)雜度
????? ??在函數(shù)的漸近增長(zhǎng)的基礎(chǔ)上忌栅，再進(jìn)一步介紹一種分析算法時(shí)間效率的方法车酣，運(yùn)用算法時(shí)間復(fù)雜度進(jìn)行判斷。
?算法時(shí)間復(fù)雜度的定義為：在進(jìn)行算法分析時(shí)索绪，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)湖员，進(jìn)而分析T（n）隨n的變化情況并確定T（n）的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度瑞驱，也就是算法的時(shí)間量度娘摔，記作：T（n）=O（f（n））。它表示問(wèn)題規(guī)模n的增大唤反，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同凳寺，稱作算法的時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度彤侍。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)肠缨。
（）
推導(dǎo)大O階：
1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)盏阶。
2晒奕、在修改后的運(yùn)行次數(shù)中，只保留最高階項(xiàng)。
3脑慧、如果最高階項(xiàng)存在不是1惠窄，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
得到的結(jié)果就是大O階漾橙。
八杆融、常見(jiàn)的時(shí)間復(fù)雜度
常見(jiàn)的時(shí)間復(fù)雜度及其所耗費(fèi)的時(shí)間從小到大依次為：
O（1）
九、最壞的情況和平均情況
?對(duì)算法的分析霜运，一種方法是計(jì)算所有情況的平均值脾歇，這種時(shí)間復(fù)雜度的計(jì)算方法稱為平均時(shí)間復(fù)雜度。另一種方法是計(jì)算最壞情況的時(shí)間復(fù)雜度淘捡，這種方法稱為最壞時(shí)間復(fù)雜度藕各。一般在沒(méi)有說(shuō)明的情況下，都是指最壞時(shí)間復(fù)雜度焦除。
舉個(gè)例子激况，在一個(gè)存儲(chǔ)量為n的數(shù)據(jù)庫(kù)里查找一個(gè)數(shù)，最壞的情況是查找了n次才查到這個(gè)數(shù)膘魄，平均的情況是用了n/2次乌逐。
最壞情況運(yùn)行時(shí)間是一種保證，那就是運(yùn)行時(shí)間將不會(huì)再壞了创葡。在應(yīng)用中浙踢，這是一種最重要的需求，通常灿渴，除非特別指定洛波，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間。
????? ? 平均運(yùn)行時(shí)間是所有情況中最有意義的骚露，因?yàn)樗瞧谕倪\(yùn)行時(shí)間蹬挤。
十、算法空間復(fù)雜度
算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)棘幸，算法空間復(fù)雜度的計(jì)算公式記作：S（n）=O（f（n））,其中焰扳，n為問(wèn)題的規(guī)模，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)够话。
????? ? 通常蓝翰，我們都使用“時(shí)間復(fù)雜度”來(lái)指運(yùn)行時(shí)間的需求光绕，使用“空間復(fù)雜度”指空間需求女嘲。
