DS之算法概述

算法 算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有5個重要的特性。 (1)有窮性 一個算法必須總是(對任何合法的輸入)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)(合理的，可接受的

算法

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有5個重要的特性。

(1)有窮性 一個算法必須總是(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)(合理的，可接受的時間內(nèi))完成。

(2)確定性 算法中每一條指令必須有確切的含義，讀者理解時不會產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出。

(3)可行性 一個算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

(4)輸入 一個算法有零個或多個的輸入，這些輸入取自某個特定的對象集合。

(5)輸出 一個算法有一個或多個的輸出，這些輸出是同輸入有某些特定關(guān)系的量。

算法設(shè)計的要求

(1)正確性 算法應(yīng)當滿足具體問題的需求。

(2)可讀性 算法主要是為了人的閱讀和交流，其次才是機器執(zhí)行。可讀性有助于人對算法的理解。

(3)健壯性 當輸入數(shù)據(jù)非法時，算法也能適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生莫名其妙的輸出結(jié)果。

(4)效率與低存儲量需求 通俗地說，效率指的是算法執(zhí)行的時間。對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法效率高。存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。效率與低存儲量需求都與問題規(guī)模有關(guān)。

算法效率的度量

算法執(zhí)行時間需要通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法：

(1)事后統(tǒng)計的方法

(2)事前分析估算的方法

一個用高級程序語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素：

1，依據(jù)的算法選何種策略

2，問題的規(guī)模

3，書寫程序的語言，對于同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低。

4，編譯程序所產(chǎn)生的機器代碼的質(zhì)量

5，機器執(zhí)行指令的速度

一個算法是由控制結(jié)構(gòu)(順序，分支和循環(huán)三種)和原操作(指固有數(shù)據(jù)類型的操作)構(gòu)成的，則算法時間取決于兩者的總和效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題(或算法類型)來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。

算法的時間復(fù)雜度

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作T(n)=O(f(n)),它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。

顯然，被稱作問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。

下面通過幾個例子來說明時間復(fù)雜度

1，{ ++x; s=0; } “x增1”的語句的頻度為1，則時間復(fù)雜度為O(1)常量階

2，for(int i=1; i<=n; i++) { ++x; s+=x; } “x增1”的語句的頻度為n，則時間復(fù)雜度為O(n)線性階

3，for(int i=1; i<=n; i++)

for(int j=1; j<=n; j++) { ++x; s+=x; } “x增1”的語句的頻度為n*n，則時間復(fù)雜度為O(n*n)平方階

算法還可能呈現(xiàn)的時間復(fù)雜度有對數(shù)階，指數(shù)階等【本文來自鴻網(wǎng)互聯(lián) (http://www.68idc.cn)】。

算法的存儲空間需求

類似于算法的時間復(fù)雜度，而空間復(fù)雜度作為算法所需要存儲空間的量度，記作S(n)=O(f(n)),其中n為問題的規(guī)模(或大小)。一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令，常數(shù)，變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需要信息的輔助空間。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外空間，否則應(yīng)同時考慮輸入本身所需要空間(和輸入數(shù)據(jù)的表示形式有關(guān))。若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。

如果所占空間量依賴于特定的輸入，則除特定指明外，均按最壞情況來分析。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com