《11-計(jì)算機(jī)科學(xué)與技術(shù)》由會(huì)員分享，可在線閱讀，更多相關(guān)《11-計(jì)算機(jī)科學(xué)與技術(shù)(23頁(yè)珍藏版)》請(qǐng)?jiān)谌巳宋膸?kù)網(wǎng)上搜索。

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ),機(jī)械工業(yè)出版社2007年7月,第一部分 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ),第1章 算法 第2章 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ) 第3章 線性表及其存儲(chǔ)結(jié)構(gòu) 第4章 棧和對(duì)列 第5章 樹(shù)與二叉樹(shù) 第7章 查找與排序,數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)可以幫助我們更好地進(jìn)行程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法選擇和程序?qū)崿F(xiàn)效率。 應(yīng)用 1)語(yǔ)言編譯要使用“棧”程序中利用“棧”來(lái)實(shí)現(xiàn)函數(shù)過(guò)程的調(diào)用; 2)操作系統(tǒng)中要用隊(duì)列打印隊(duì)列，當(dāng)計(jì)算機(jī)輸出的數(shù)據(jù)用打印機(jī)打印時(shí)，由于打印機(jī)速度慢，此時(shí)可設(shè)置一個(gè)打印隊(duì)列，將打印任務(wù)逐個(gè)打印，從而避免數(shù)據(jù)丟失或打印次序混亂; 3)數(shù)據(jù)庫(kù)系統(tǒng)則使用線性表、鏈表等進(jìn)行數(shù)據(jù)管理; 4)人工智能領(lǐng)域依。

2、據(jù)問(wèn)題的差異涉及到諸如廣義表、樹(shù)、各種有向圖等；,第1章 算法,1.1 算法的基本概念 1.2算法的描述方式,1.1 算法的基本概念,所謂算法是指解題方案的準(zhǔn)確而完整的描述。 對(duì)于一個(gè)問(wèn)題，如果可以通過(guò)一個(gè)計(jì)算機(jī)程序，在有限的存儲(chǔ)空間內(nèi)，運(yùn)行有限長(zhǎng)的時(shí)間而得到正確的結(jié)果，則稱這個(gè)問(wèn)題是算法可解的。 1.算法的基本特征 1)可行性：算法描述的每一個(gè)步驟必須能夠?qū)崿F(xiàn)，且能夠達(dá)到預(yù)期的目的； 2)確定性：算法中的每一個(gè)步驟，必須經(jīng)過(guò)明確的定義，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出,相同的輸出； 3)有窮性：算法必須能在有限的時(shí)間內(nèi)做完 即算法必須能在執(zhí)行有限個(gè)步驟之后終。

3、止； 4)輸入：具有零個(gè)或多個(gè)輸入，它們是算 法開(kāi)始前的初始量； 5)輸出：至少產(chǎn)生一個(gè)輸出，它們是與輸入 有某種關(guān)系的量，是算法的執(zhí)行結(jié)果。,2.算法的基本要素 1)算法中對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作 通常，基本運(yùn)算和操作有以下四類： 算術(shù)運(yùn)算：有加、減、乘、除等運(yùn)算； 邏輯運(yùn)算：有“與”、“或”、“非”等運(yùn)算；,關(guān)系運(yùn)算：有“大于”、“小于”、“等于”、“不等于”等運(yùn)算； 數(shù)據(jù)傳輸：有賦值、輸入、輸出等操作。,2)算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序，稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。一。

4、個(gè)算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。,3. 算法設(shè)計(jì)的基本方法 算法設(shè)計(jì)的基本方法有列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)和回溯法。 1)列舉法 列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉所有的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?#xff0c;哪些是不需要的。因此，列舉法常用于解決“是否存在”或“有多少可能”等類型的問(wèn)題，例如求解不定方程的問(wèn)題。,2)歸納法 歸納法的基本思想是，通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。,3)遞推 所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)。

5、而確定。,4)遞歸,人們?cè)诮鉀Q一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度，一般總是將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解。但是當(dāng)解決了分解到最后的那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的基本思想。 找偽幣：假設(shè)16枚金幣中有一枚是偽造的,真假金幣的區(qū)別僅是重量不同,利用一個(gè)沒(méi)有砝碼的天平作工具,如何快速找出這枚偽造的金幣?,)減半遞推技術(shù) 所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；這里所謂“遞推”，是指重復(fù)“減半”的過(guò)程。 猜數(shù)游戲,)回溯法 回溯法的基本思想是，通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線。

6、索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解；若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。,1.2 算法復(fù)雜度及算法的描述方式 1.算法復(fù)雜度 算法復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。,1)算法的時(shí)間復(fù)雜度* 所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 算法的工作量，一般用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即 算法的工作量T(n) 其中，n是問(wèn)題的規(guī)模。例如，兩個(gè)n階矩陣相乘，所需要的基本運(yùn)算(即兩個(gè)實(shí)數(shù)的乘法)次數(shù)是n的函數(shù)T(n)。算法如下：,for(i=0;in;i+) /*執(zhí)行n+1次*。

7、/ for(j=0;jn;j+)/*執(zhí)行n(n+1)次*/ cij=0; /*執(zhí)行n2 次*/ for(k=0;kn;k+)/*執(zhí)行n2(n+1)次*/ cij=cij+aik*bkj; /*執(zhí)行n3次*/ 一條語(yǔ)句在算法中被重復(fù)執(zhí)行的次數(shù)，稱為該語(yǔ)句的頻度。 這里，T(n)=2n3 + 3 n2 + 2n +1是n的函數(shù),顯然，T(n)/n3 2 (當(dāng)n 時(shí))。 由高等數(shù)學(xué)中無(wú)窮大的比較的知識(shí)知，T(n)與n3 的量級(jí)(數(shù)量級(jí))相同，即時(shí)間復(fù)雜度T(n)的量級(jí)為O(n3)，記為T(n)=O(n3)。 在具體分析時(shí)，可做如下處理： 若語(yǔ)句很少執(zhí)行且與規(guī)模n無(wú)關(guān)，則可忽略不計(jì)； 若所有語(yǔ)句都與規(guī)。

8、模n無(wú)關(guān)，則即使有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)，故時(shí)間復(fù)雜度的量級(jí)也只是O(n0)=O(1)；,一般可只考慮與程序規(guī)模有關(guān)的頻度最大的語(yǔ)句，如循環(huán)語(yǔ)句的循環(huán)體，多重循環(huán)的內(nèi)循環(huán)等。,常見(jiàn)時(shí)間復(fù)雜度的量級(jí)有：常數(shù)階O(1)、線性階O(n)、平方階O(n2)、指數(shù)階O(2n )、對(duì)數(shù)階O(log2n)、線性對(duì)數(shù)階O(nlog2n)。通常認(rèn)為，具有指數(shù)階量級(jí)的算法是實(shí)際不可計(jì)算的，而量級(jí)低于平方階的算法是高效率的。 今后若無(wú)特別說(shuō)明，就將算法時(shí)間復(fù)雜度的量級(jí)，看作算法的時(shí)間復(fù)雜度。即某算法的時(shí)間復(fù)雜度是指該算法時(shí)間復(fù)雜度的量級(jí)。,例1-1 說(shuō)明下列各個(gè)程序段的時(shí)間復(fù)雜度。 /*交換a。

9、和b的內(nèi)容*/ t=a; a=b; b=t; /*求n以內(nèi)所有2的冪次數(shù)的和，即 1+21+22+2k，2kn */ sum=0; for(i=1;i=n;i*=2) sum+=i; 說(shuō)明：在程序段中，三條語(yǔ)句的執(zhí)行次數(shù)均為1，與規(guī)模n無(wú)關(guān)，故可知其時(shí)間復(fù)雜度為O(1)。,在程序段中，執(zhí)行次數(shù)最多的語(yǔ)句是循環(huán)體sum+=i，它執(zhí)行的次數(shù)未知，顯然不是n次，若設(shè)為k次，由于2kn，所以有klog2n故時(shí)間復(fù)雜度為O(log2n)。,在具體分析一個(gè)算法的工作量時(shí)，還會(huì)存在這樣的問(wèn)題：對(duì)于一個(gè)固定的規(guī)模，算法所執(zhí)行的基本運(yùn)算次數(shù)，還可能與特定的輸入有關(guān)，而實(shí)際上又不可能將所有可能情況的算法所執(zhí)行的基。

10、本運(yùn)算次數(shù)都列舉出來(lái)。例如：在長(zhǎng)度為n的一維數(shù)組中，采用順序搜索法查找值為x的元素，在這個(gè)問(wèn)題的算法中,其基本運(yùn)算(即比較)的次數(shù)與具體的被查找(輸入)值x有關(guān)?？紤]到這種情況，通常采用平均性態(tài)和最壞情況復(fù)雜性兩種方式，來(lái)確定一個(gè)算法的工作量。,平均性態(tài) 所謂平均性態(tài)，是指在規(guī)模為n時(shí)，用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。 設(shè)x是所有可能輸入中的某個(gè)特定輸入，p(x)是x出現(xiàn)的概率(即輸入為x的概率)，,t(x)是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為： ， xDn , Dn表示當(dāng)規(guī)模為 n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。, 最壞情況復(fù)雜性 所。

11、謂最壞情況復(fù)雜性，是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)，定義為： ， xDn 顯然W(n)的計(jì)算要比A(n)的計(jì)算方便得多。,2)算法的空間復(fù)雜度 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。,2.算法的描述方式 任何算法都必須用某種方法描述出來(lái)，其中常用的就是語(yǔ)言描述。根據(jù)描述語(yǔ)言的不同，算法分三類： 1)程序設(shè)計(jì)語(yǔ)言算法。采用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述，可直接在計(jì)算機(jī)上運(yùn)行，從而使給定問(wèn)題在有限時(shí)間內(nèi)被機(jī)械的求解。,2)偽語(yǔ)言算法。采用偽程序設(shè)計(jì)語(yǔ)言描述，不能直接在計(jì)算機(jī)上運(yùn)行。偽語(yǔ)言介于程序設(shè)計(jì)語(yǔ)言和自然語(yǔ)言之間，它忽略程序設(shè)計(jì)語(yǔ)言中一些嚴(yán)格的語(yǔ)法規(guī)則和細(xì)節(jié)描述，因此偽語(yǔ)言描述可突出算法設(shè)計(jì)的主要方面而不是語(yǔ)法細(xì)節(jié)。,3)非形式算法。采用自然語(yǔ)言，同時(shí)還可使用程序設(shè)計(jì)語(yǔ)言或偽程序設(shè)計(jì)語(yǔ)言(如流程控制語(yǔ)句while、for、if等)描述。 算法除了用語(yǔ)言描述外，實(shí)際上還有一種圖形描述方法，如流程圖、N-S圖等。,不管算法用什么方法描述，它最終都要轉(zhuǎn)換為程序才能在計(jì)算機(jī)上運(yùn)行。容易看出上述幾種描述方法的可讀性依次增強(qiáng)，但可讀性越強(qiáng)，離最終程序的距離越遠(yuǎn)。本書(shū)采用C語(yǔ)言作為描述工具。

總結(jié)

以上是生活随笔為你收集整理的11计算机,11-计算机科学与技术的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。