2011計算機(jī)等考二級公共基礎(chǔ)知識講義：第1章(1)

　　2011計算機(jī)等考二級公共基礎(chǔ)知識講義目錄

　　　第一章　數(shù)據(jù)結(jié)構(gòu)與算法

　　　第二章　程序設(shè)計基礎(chǔ)

　　　第三章　軟件工程基礎(chǔ)

　　　第四章　數(shù)據(jù)庫設(shè)計基礎(chǔ)

　　點(diǎn)擊進(jìn)入：2011計算機(jī)等考二級公共基礎(chǔ)知識講義匯總>>

第一章 數(shù)據(jù)結(jié)構(gòu)與算法

　　1.1 算法

　　1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。

　　*算法不等于程序，也不等于計算方法。程序的編制不可能優(yōu)于算法的設(shè)計(注釋1) 。

　　2、算法的基本特征

　　(1)可行性。針對實(shí)際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。

　　(2)確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。

　　(3)有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。

　　(4)擁有足夠的情報。算法中各種運(yùn)算總是要施加到各個運(yùn)算對象上，而這些運(yùn)算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情報時，此算法才是有效的;而當(dāng)提供的情報不夠時，算法可能無效。

　　*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟�義運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

　　3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。

　　(1)算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。

　　(2)算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。

　　注釋1：這是因?yàn)樵诰帉懗绦驎r要受到計算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題。

　　相關(guān)推薦：

　　2011計算機(jī)等考二級公共基礎(chǔ)知識要點(diǎn)匯總

　　2010年9月計算機(jī)等級考試成績查詢時間匯總

　　2011年上半年計算機(jī)等級考試報名時間匯總