算法分析

算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。 算法（Algorithm）是解題的步驟，可以把算法定義成解一確定類問題的任意一種特殊的方法。在計算機科學中，算法要用計算機算法語言描述，算法代表用計算機解一類問題的精確、有效的方法。

基本介紹

• 中文名：算法分析
• 外文名：Algorithm analysis
• 套用：算法最佳化
• 網路套用：引擎的算法套用
• 主要對象：時間複雜度、空間複雜度
• 作用：評價算法的好壞

簡介

算法是一組有窮的規則，它們規定了解決某一特定類型問題的一系列運算，是對解題方案內的準確與完整地描述。制定一個算法，一般要經過設計、確認、分析、編碼、測試、調試、計時等階段。

算法+數據結構=程式，求解一個給定的可計算或可解的問題，不同的人可以編寫出不同的程式，來解決同一個問題，這裡存在兩個問題：一是與計算方法密切相關的算法問題；二是程式設計的技術問題。算法和程式之間存在密切的關係。分析算法可以預測這一算法適合在什麼樣的環境中有效地運行，對解決同一問題的不同算法的有效性作出比較。

通常對於一個實際問題的解決，可以提出若干個算法，如何從這些可行的算法中找出最有效的算法呢？或者有了一個解決實際問題的算法後，如何來評價它的好壞呢？這些問題都需要通過算法分析來確定。評價算法分析性能的標準主要從算法執行時間和占用存儲空間兩個方面進行考慮，即通過分析算法執行所需要的時間和存儲空間來判斷一個算法的優劣。

時間複雜度

一個程式的時間複雜度是指程式運行從開始到結束所需要的時間。

影響因素

一個算法是由控制結構（順序、分支和循環3種）和原操作（指固定數據類型的操作）構成的，其執行時間取決於兩者的綜合效果。為了便於比較同一問題的不同算法，通常的做法是：從算法中選取一種對於所研究的問題來說基本運算的原操作，以該原操作重複執行的次數作為算法的時間度量。一般情況下，算法中原操作重複執行次數是規模n的某個函式T(n)。許多時候要精確的計算T(n)是困難的，引入漸進時間複雜度在數量上估計一個算法的執行時間，也能夠達到分析算法的目的。

計算方法

計算時間複雜度的時候，主要考慮算法中最高階項的開銷，只要找出算法中最高階的複雜度，就可以忽略低階和常數的複雜度。

引入數學符號“O”來估算算法時間複雜度，漸進時間複雜度的表示方法：F(n)=O(g(n))，其定義為，若F(n)和g(n)是定義在正整數集合上的兩個函式，則F(n)=O(g(n))表示存在正的常數C和 ，使得當 時，都滿足 。換句話說，就是這兩個函式當整形自變數n趨於無窮大時，兩者的比值是一個不等於0的常數。

當要計算某個算法的時間複雜度F(n)時，可以找一個更簡單的、階數相同的簡單算法g(n)等同計算，這裡的g(n)是指替代函式，它具有和原算法一樣更高階複雜度。

例如，一個程式的實際執行時間為： ，則 。使用O記號表示的算法的時間複雜度，稱為算法的漸進時間複雜度。

常見的漸進時間複雜度

通常用O(1)表示常數計算時間。常見的漸進時間複雜度有：

規則

為了便於估算一個算法的時間複雜度，我們約定一下幾條可操作的規則：

（1）讀寫單個常量或單個變數、賦值、算術運算、關係運算、邏輯運算等，計為一個單位時間。

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

（3）條件語句if(C)s1 else s2，執行時間為（條件C的執行時間）+（語句塊s1和s2中執行時間最長的那個時間）。

（4）switch...case語句的執行時間是所有case子句中，執行時間最長的語句塊。

（5）訪問一個數據的單個元素或一個結構體變數的單個元素只需要一個單位時間。

（6）執行一個for循環語句需要的時間等於執行該循環體所需要時間乘上循環次數。

（7）執行一個while(C){s}循環語句或者執行一個do{s} while(C)語句，需要的時間等於計算條件表達式C的時間與執行循環s的時間之和再乘以循環的次數。

（8）對於嵌套結構，算法的時間複雜度由嵌套最深層語句的執行次數決定的。

（9）對於函式調用語句，它們需要的時間包括兩部分，一部分用於實現控制轉移，另一部分用於執行函式本身。

空間複雜度

一個算法的空間複雜度是指程式運行從開始到結束所需的存儲空間大小。程式的一次運行是針對所求解的問題的某一特定實例而言的。例如，求解排序問題的排序算法每次執行是對一組特定個數的元素進行排序。對該組元素的排序是排序問題的一個實例。元素個數可視為該實例的特徵。程式運行所需要的存儲空間主要包括兩部分。

固定部分

這部分空間與所處理數據的大小和個數無關，或者稱與問題的實例的特徵無關。主要包括程式代碼、常量、簡單變數、定長成分的結構變數所占的空間。

可變部分

這部分空間大小與算法在某次執行中處理的特定數據的大小和規模有關。例如100個數據元素的排序算法與1000個數據元素的排序算法所需要的存儲空間顯然是不同的。

算法在運行過程中臨時占用的存儲空間隨算法的不同而異。有的算法只需要占用少量的存儲空間，而且不隨問題規模的大小而改變，有的算法需要占用的存儲空間數隨著問題規模n的增大而增大，此時按照最壞情況來分析

套用

在查找引擎最佳化範疇裡邊有一個疑問常常讓人感受捉摸不透，到底是什麼樣的排序要素結尾決議了網頁的排名。而每個查找引擎公司都將其的查找引擎算法維護的極端緊密，只要很少很少的一有些的公司能有時機看到這些算法的全貌。並且就算是有時機看到這些算法的真實容貌，要想領悟到話，還得具有深沉的數學功底。這使得對查找引擎最佳化整個概念的曉得變得很艱難

算法套用和問題解決

為了更快的回來查找成果給用戶，查找引擎公司通常都會將巨大的運算簡化，查找引擎所運用的這些算法都會設定一個用於比擬判別網站價值的根底準則。不一樣的查找引擎所運用的基準是不一樣的。例如，在Google的算法中就運用了200多個要從來構建這個基準。經過很多查找引擎愛好者的研討與查找引擎的共享，大家也大約的曉得了查找引擎算法中的重要有些。可是要想曉得查找引擎的各個細節那是不能夠的工作，更何況Google簡直每天都會對算法做出很多的修改。有些修正會形成很大的影響，有些則僅僅一些細微的修正。查找算法的不斷改變使得大家更難知曉算法的各個細節。

算法最佳化

在確定了算法之後，在構建網站(或是為SEO更新網站)時就能有一些能夠遵照的準則。在這些準則中，最重要的就是要以人為本，而不要為查找引擎描繪網站。所以，若是創立的網站是關於春季休假的，就應該為用戶供給與春季休假有關的信息和連線。在爬蟲檢索網站時，若是網站中含有指向機票預訂網站、假目網站、花園展現網站或其他與春季休假有關的網站的連線，爬蟲就會跟蹤這些連線，並經過算法判別這些網站的關聯性。若是這些網站都與春季休假有親近的聯繫，網站就能取得較高的排名。若是網站連線的都是一些無關的網站，就有能夠查找爬蟲視為連線場，網站排名會很差，乃至遭到禁止。其間難以確定的是，究竟網站中必須有多少關聯網站的連線，又能夠有多少無關網站的連線。從常理上說，若是描繪一個關於春季休假的網頁，抱負的狀況是進出這個網頁的連線來自關聯的網頁。廣告能夠是一個破例，但這會被明確地標明為廣告。另一種狀況就是網站上一切的連線都是指向無關網站的廣告。這樣的網頁顯然是不受歡迎的，網頁在查找引擎中的排名天然也會降低。

關鍵字也有相同的疑問。查找引擎偏心關鍵字密度較高的網站。無論是什麼查找引擎，內容都是重要的，但在怎么判別內容對網頁排名的影響這個疑問上，各個查找引擎都有不一樣的辦法。相同，元標籤在各個查找引擎中的重要性也不盡相同。