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

　　2011計算機等考二級公共基礎知識講義目錄

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

　　　第二章　程序設計基礎

　　　第三章　軟件工程基礎

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

　　點擊進入：2011計算機等考二級公共基礎知識講義匯總>>

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

　　1.1 算法

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

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

　　2、算法的基本特征

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

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

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

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

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

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

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

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

　　注釋1：這是因為在編寫程序時要受到計算機系統(tǒng)運行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細節(jié)問題。

　　相關(guān)推薦：

　　2011計算機等考二級公共基礎知識要點匯總

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

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