[科普中國(guó)]-算法分析

簡(jiǎn)介

算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算，是對(duì)解題方案內(nèi)的準(zhǔn)確與完整地描述。制定一個(gè)算法，一般要經(jīng)過(guò)設(shè)計(jì)、確認(rèn)、分析、編碼、測(cè)試、調(diào)試、計(jì)時(shí)等階段。1

算法+數(shù)據(jù)結(jié)構(gòu)=程序，求解一個(gè)給定的可計(jì)算或可解的問(wèn)題，不同的人可以編寫出不同的程序，來(lái)解決同一個(gè)問(wèn)題，這里存在兩個(gè)問(wèn)題：一是與計(jì)算方法密切相關(guān)的算法問(wèn)題；二是程序設(shè)計(jì)的技術(shù)問(wèn)題。算法和程序之間存在密切的關(guān)系。分析算法可以預(yù)測(cè)這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對(duì)解決同一問(wèn)題的不同算法的有效性作出比較。1

通常對(duì)于一個(gè)實(shí)際問(wèn)題的解決，可以提出若干個(gè)算法，如何從這些可行的算法中找出最有效的算法呢？或者有了一個(gè)解決實(shí)際問(wèn)題的算法后，如何來(lái)評(píng)價(jià)它的好壞呢？這些問(wèn)題都需要通過(guò)算法分析來(lái)確定。評(píng)價(jià)算法分析性能的標(biāo)準(zhǔn)主要從算法執(zhí)行時(shí)間和占用存儲(chǔ)空間兩個(gè)方面進(jìn)行考慮，即通過(guò)分析算法執(zhí)行所需要的時(shí)間和存儲(chǔ)空間來(lái)判斷一個(gè)算法的優(yōu)劣。2

時(shí)間復(fù)雜度一個(gè)程序的時(shí)間復(fù)雜度是指程序運(yùn)行從開(kāi)始到結(jié)束所需要的時(shí)間。

影響因素一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固定數(shù)據(jù)類型的操作）構(gòu)成的，其執(zhí)行時(shí)間取決于兩者的綜合效果。為了便于比較同一問(wèn)題的不同算法，通常的做法是：從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般情況下，算法中原操作重復(fù)執(zhí)行次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。許多時(shí)候要精確的計(jì)算T(n)是困難的，引入漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間，也能夠達(dá)到分析算法的目的。3

計(jì)算方法計(jì)算時(shí)間復(fù)雜度的時(shí)候，主要考慮算法中最高階項(xiàng)的開(kāi)銷，只要找出算法中最高階的復(fù)雜度，就可以忽略低階和常數(shù)的復(fù)雜度。3

引入數(shù)學(xué)符號(hào)“O”來(lái)估算算法時(shí)間復(fù)雜度，漸進(jìn)時(shí)間復(fù)雜度的表示方法：F(n)=O(g(n))，其定義為，若F(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則F(n)=O(g(n))表示存在正的常數(shù)C和 ，使得當(dāng) 時(shí)，都滿足 。換句話說(shuō)，就是這兩個(gè)函數(shù)當(dāng)整形自變量n趨于無(wú)窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。3

當(dāng)要計(jì)算某個(gè)算法的時(shí)間復(fù)雜度F(n)時(shí)，可以找一個(gè)更簡(jiǎn)單的、階數(shù)相同的簡(jiǎn)單算法g(n)等同計(jì)算，這里的g(n)是指替代函數(shù)，它具有和原算法一樣更高階復(fù)雜度。3

例如，一個(gè)程序的實(shí)際執(zhí)行時(shí)間為： ，則 。使用O記號(hào)表示的算法的時(shí)間復(fù)雜度，稱為算法的漸進(jìn)時(shí)間復(fù)雜度。3

常見(jiàn)的漸進(jìn)時(shí)間復(fù)雜度通常用O(1)表示常數(shù)計(jì)算時(shí)間。常見(jiàn)的漸進(jìn)時(shí)間復(fù)雜度有：

規(guī)則為了便于估算一個(gè)算法的時(shí)間復(fù)雜度，我們約定一下幾條可操作的規(guī)則：

（1）讀寫單個(gè)常量或單個(gè)變量、賦值、算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算等，計(jì)為一個(gè)單位時(shí)間。

（2）條件語(yǔ)句if(C){s}，執(zhí)行時(shí)間為（條件C的執(zhí)行時(shí)間）+（語(yǔ)句塊s的執(zhí)行時(shí)間）。

（3）條件語(yǔ)句if(C)s1 else s2，執(zhí)行時(shí)間為（條件C的執(zhí)行時(shí)間）+（語(yǔ)句塊s1和s2中執(zhí)行時(shí)間最長(zhǎng)的那個(gè)時(shí)間）。

（4）switch...case語(yǔ)句的執(zhí)行時(shí)間是所有case子句中，執(zhí)行時(shí)間最長(zhǎng)的語(yǔ)句塊。

（5）訪問(wèn)一個(gè)數(shù)據(jù)的單個(gè)元素或一個(gè)結(jié)構(gòu)體變量的單個(gè)元素只需要一個(gè)單位時(shí)間。

（6）執(zhí)行一個(gè)for循環(huán)語(yǔ)句需要的時(shí)間等于執(zhí)行該循環(huán)體所需要時(shí)間乘上循環(huán)次數(shù)。

（7）執(zhí)行一個(gè)while(C){s}循環(huán)語(yǔ)句或者執(zhí)行一個(gè)do{s} while(C)語(yǔ)句，需要的時(shí)間等于計(jì)算條件表達(dá)式C的時(shí)間與執(zhí)行循環(huán)s的時(shí)間之和再乘以循環(huán)的次數(shù)。

（8）對(duì)于嵌套結(jié)構(gòu)，算法的時(shí)間復(fù)雜度由嵌套最深層語(yǔ)句的執(zhí)行次數(shù)決定的。

（9）對(duì)于函數(shù)調(diào)用語(yǔ)句，它們需要的時(shí)間包括兩部分，一部分用于實(shí)現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行函數(shù)本身。3

空間復(fù)雜度一個(gè)算法的空間復(fù)雜度是指程序運(yùn)行從開(kāi)始到結(jié)束所需的存儲(chǔ)空間大小。程序的一次運(yùn)行是針對(duì)所求解的問(wèn)題的某一特定實(shí)例而言的。例如，求解排序問(wèn)題的排序算法每次執(zhí)行是對(duì)一組特定個(gè)數(shù)的元素進(jìn)行排序。對(duì)該組元素的排序是排序問(wèn)題的一個(gè)實(shí)例。元素個(gè)數(shù)可視為該實(shí)例的特征。程序運(yùn)行所需要的存儲(chǔ)空間主要包括兩部分。3

固定部分這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無(wú)關(guān)，或者稱與問(wèn)題的實(shí)例的特征無(wú)關(guān)。主要包括程序代碼、常量、簡(jiǎn)單變量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。3

可變部分這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如100個(gè)數(shù)據(jù)元素的排序算法與1000個(gè)數(shù)據(jù)元素的排序算法所需要的存儲(chǔ)空間顯然是不同的。3

算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異。有的算法只需要占用少量的存儲(chǔ)空間，而且不隨問(wèn)題規(guī)模的大小而改變，有的算法需要占用的存儲(chǔ)空間數(shù)隨著問(wèn)題規(guī)模n的增大而增大，此時(shí)按照最壞情況來(lái)分析

應(yīng)用在查找引擎優(yōu)化范疇里邊有一個(gè)疑問(wèn)常常讓人感受捉摸不透，到底是什么樣的排序要素結(jié)尾決議了網(wǎng)頁(yè)的排名。而每個(gè)查找引擎公司都將其的查找引擎算法維護(hù)的極端緊密，只要很少很少的一有些的公司能有時(shí)機(jī)看到這些算法的全貌。并且就算是有時(shí)機(jī)看到這些算法的真實(shí)容貌，要想領(lǐng)悟到話，還得具有深沉的數(shù)學(xué)功底。這使得對(duì)查找引擎優(yōu)化整個(gè)概念的曉得變得很艱難

算法應(yīng)用和問(wèn)題解決為了更快的回來(lái)查找成果給用戶，查找引擎公司通常都會(huì)將巨大的運(yùn)算簡(jiǎn)化，查找引擎所運(yùn)用的這些算法都會(huì)設(shè)置一個(gè)用于比擬判別網(wǎng)站價(jià)值的根底準(zhǔn)則。不一樣的查找引擎所運(yùn)用的基準(zhǔn)是不一樣的。例如，在Google的算法中就運(yùn)用了200多個(gè)要從來(lái)構(gòu)建這個(gè)基準(zhǔn)。經(jīng)過(guò)很多查找引擎愛(ài)好者的研討與查找引擎的共享，大家也大約的曉得了查找引擎算法中的重要有些。可是要想曉得查找引擎的各個(gè)細(xì)節(jié)那是不能夠的工作，更何況Google簡(jiǎn)直每天都會(huì)對(duì)算法做出很多的修改。有些修正會(huì)形成很大的影響，有些則僅僅一些細(xì)微的修正。查找算法的不斷改變使得大家更難知曉算法的各個(gè)細(xì)節(jié)。

算法優(yōu)化在確定了算法之后，在構(gòu)建網(wǎng)站(或是為SEO更新網(wǎng)站)時(shí)就能有一些能夠遵照的準(zhǔn)則。在這些準(zhǔn)則中，最重要的就是要以人為本，而不要為查找引擎描繪網(wǎng)站。所以，若是創(chuàng)立的網(wǎng)站是關(guān)于春季休假的，就應(yīng)該為用戶供給與春季休假有關(guān)的信息和連接。在爬蟲(chóng)檢索網(wǎng)站時(shí)，若是網(wǎng)站中含有指向機(jī)票預(yù)訂網(wǎng)站、假目網(wǎng)站、花園展現(xiàn)網(wǎng)站或其他與春季休假有關(guān)的網(wǎng)站的連接，爬蟲(chóng)就會(huì)跟蹤這些連接，并經(jīng)過(guò)算法判別這些網(wǎng)站的關(guān)聯(lián)性。若是這些網(wǎng)站都與春季休假有親近的聯(lián)系，網(wǎng)站就能取得較高的排名。若是網(wǎng)站連接的都是一些無(wú)關(guān)的網(wǎng)站，就有能夠查找爬蟲(chóng)視為連接場(chǎng)，網(wǎng)站排名會(huì)很差，乃至遭到屏蔽。其間難以確定的是，究竟網(wǎng)站中必須有多少關(guān)聯(lián)網(wǎng)站的連接，又能夠有多少無(wú)關(guān)網(wǎng)站的連接。從常理上說(shuō)，若是描繪一個(gè)關(guān)于春季休假的網(wǎng)頁(yè)，抱負(fù)的狀況是進(jìn)出這個(gè)網(wǎng)頁(yè)的連接來(lái)自關(guān)聯(lián)的網(wǎng)頁(yè)。廣告能夠是一個(gè)破例，但這會(huì)被明確地標(biāo)明為廣告。另一種狀況就是網(wǎng)站上一切的連接都是指向無(wú)關(guān)網(wǎng)站的廣告。這樣的網(wǎng)頁(yè)顯然是不受歡迎的，網(wǎng)頁(yè)在查找引擎中的排名天然也會(huì)降低。

關(guān)鍵詞也有相同的疑問(wèn)。查找引擎偏心關(guān)鍵詞密度較高的網(wǎng)站。無(wú)論是什么查找引擎，內(nèi)容都是重要的，但在怎么判別內(nèi)容對(duì)網(wǎng)頁(yè)排名的影響這個(gè)疑問(wèn)上，各個(gè)查找引擎都有不一樣的辦法。相同，元標(biāo)簽在各個(gè)查找引擎中的重要性也不盡相同。