大學(xué)計(jì)算機(jī)算法基礎(chǔ)

關(guān)于大學(xué)計(jì)算機(jī)算法基礎(chǔ)第1頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/282§4.1算法基本概念1.算法的概念為解決一個(gè)問(wèn)題而采取的方法和步驟，稱(chēng)為算法。用計(jì)算機(jī)來(lái)解決問(wèn)題的方法和步驟，稱(chēng)為計(jì)算機(jī)算法。分為數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。第2頁(yè)，共25頁(yè)，2023年，2月20日，星期三§4.2算法的組成要素一個(gè)算法含有兩大要素：操作步驟：對(duì)于計(jì)算機(jī)算法而言，包括組成算法的各條指令，也就是對(duì)數(shù)據(jù)的運(yùn)算和操作?？刂平Y(jié)構(gòu)：控制算法中各操作步驟地執(zhí)行順序。通常有三種結(jié)構(gòu)：順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)第3頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/284控制結(jié)構(gòu)及算法舉例1、順序結(jié)構(gòu)：例1：求圓的面積的算法設(shè)r表示圓的半徑，s表示圓的面積步驟1：輸入半徑r的值步驟2：s=3.14×r×r步驟3：輸出s的值多個(gè)步驟由上到下依次執(zhí)行，順序不能打亂，稱(chēng)為順序結(jié)構(gòu)第4頁(yè)，共25頁(yè)，2023年，2月20日，星期三2、選擇結(jié)構(gòu)：例2：求兩個(gè)整數(shù)a和b中的大者的算法Ｓ１：輸入a、b的值Ｓ２：如果a＞b，則執(zhí)行S3；否則轉(zhuǎn)去執(zhí)行S4Ｓ３：輸出a的值，結(jié)束Ｓ４：輸出b的值，結(jié)束其中，Ｓ３和Ｓ４根據(jù)條件只能執(zhí)行一個(gè)，稱(chēng)為選擇結(jié)構(gòu)第5頁(yè)，共25頁(yè)，2023年，2月20日，星期三3、循環(huán)結(jié)構(gòu)例3：求出50！的算法設(shè)t為被乘數(shù)，i為乘數(shù)s1：使t=1s2：使i=2s3：t×i→ts4：i+1→is5：轉(zhuǎn)去執(zhí)行s3s6:輸出t的值當(dāng)i≤50時(shí)，為下一次乘法做準(zhǔn)備重復(fù)執(zhí)行多次，循環(huán)結(jié)構(gòu)第6頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/287

順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)是表示一個(gè)算法的基本結(jié)構(gòu)。 由以上3種基本結(jié)構(gòu)組成的算法，稱(chēng)為“結(jié)構(gòu)化”的算法，可以解決任何復(fù)雜的問(wèn)題。第7頁(yè)，共25頁(yè)，2023年，2月20日，星期三§4.3算法的基本特征1）有窮性算法中的步驟是有限的2）可行性算法中的每一個(gè)步驟必須是可執(zhí)行的3）確定性算法中的每一個(gè)步驟必須是含義確切的4）有零個(gè)或多個(gè)輸入5）有一個(gè)或多個(gè)輸出第8頁(yè)，共25頁(yè)，2023年，2月20日，星期三§4.3算法的表示方法自然語(yǔ)言流程圖偽代碼計(jì)算機(jī)編程語(yǔ)言第9頁(yè)，共25頁(yè)，2023年，2月20日，星期三算法的流程圖表示法傳統(tǒng)流程圖第10頁(yè)，共25頁(yè)，2023年，2月20日，星期三順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)流程圖第11頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/2812例如：50！的流程圖開(kāi)始t=1i=2t=t×ii=i+1i<=50輸出t結(jié)束YN第12頁(yè)，共25頁(yè)，2023年，2月20日，星期三N-S圖：三種控制結(jié)構(gòu)的N-S圖第13頁(yè)，共25頁(yè)，2023年，2月20日，星期三1=＞t2=＞ii×t=＞ti+1=＞i直到i＞50輸出結(jié)果50！的N-S圖第14頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/2815算法的偽代碼表示法偽代碼描述50！：1→t2→iwhilei<=50{t*i→ti+1→i}printt用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法第15頁(yè)，共25頁(yè)，2023年，2月20日，星期三算法的計(jì)算機(jī)語(yǔ)言表示法計(jì)算機(jī)語(yǔ)言（C語(yǔ)言）描述50！：#include<stdio.h>voidmain(){ doublet,i; t=1;i=2; while(i<=50) { t=t*i; i=i+1; } printf(“%.0f”,t);

}必須嚴(yán)格遵守計(jì)算機(jī)語(yǔ)言的語(yǔ)法規(guī)則第16頁(yè)，共25頁(yè)，2023年，2月20日，星期三§4.5常用的算法介紹列舉法：根據(jù)提出的問(wèn)題，列舉所有可能情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要。例如：求水仙花?shù)。遞推法：從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。遞歸法：將問(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)行綜合，這就是遞歸的基本思想。

回溯法：通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索逐步試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線(xiàn)再逐步試探。

第17頁(yè)，共25頁(yè)，2023年，2月20日，星期三§4.6算法的復(fù)雜度解決一個(gè)問(wèn)題，可以有很多算法，如何評(píng)價(jià)一個(gè)算法的好壞？首先算法正確，具有算法的5個(gè)基本特征還需考慮：執(zhí)行算法消耗的時(shí)間執(zhí)行算法消耗的存儲(chǔ)空間具有可讀性，易于理解健壯性第18頁(yè)，共25頁(yè)，2023年，2月20日，星期三評(píng)價(jià)方法：事前估算事后統(tǒng)計(jì)評(píng)價(jià)結(jié)果：稱(chēng)為“算法復(fù)雜度”算法復(fù)雜度可以分為時(shí)間復(fù)雜度和空間復(fù)雜度第19頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/28201.算法的時(shí)間復(fù)雜度通常把算法中進(jìn)行簡(jiǎn)單操作的次數(shù)的多少稱(chēng)為算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度往往是問(wèn)題規(guī)模的函數(shù)，即

T(n)=O(f(n))

其中，n表示問(wèn)題的規(guī)模,f(n)為問(wèn)題的規(guī)模函數(shù)

例如：求n的階乘算法的時(shí)間復(fù)雜度為：

T(n)=n-1

通常表示：T(n)=O(n)第20頁(yè)，共25頁(yè)，2023年，2月20日，星期三算法的時(shí)間復(fù)雜度還跟問(wèn)題的輸入數(shù)據(jù)有關(guān)，所以算法的時(shí)間復(fù)雜度可以用兩種形式表達(dá)：平均時(shí)間復(fù)雜度最壞情況時(shí)間復(fù)雜度第21頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/28大學(xué)計(jì)算機(jī)基礎(chǔ)22平均時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度能夠計(jì)算出所有輸入對(duì)應(yīng)的算法時(shí)間復(fù)雜度的平均值。若用t(x)表示輸入為x時(shí)的算法時(shí)間復(fù)雜度，用E(x)表示出現(xiàn)輸入x的數(shù)學(xué)期望，則算法平均時(shí)間復(fù)雜度A(n)可以表示為：第22頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/2823最壞情況時(shí)間復(fù)雜度最壞情況時(shí)間復(fù)雜度是指在所有輸入對(duì)應(yīng)的算法時(shí)間復(fù)雜度中運(yùn)算次數(shù)最多的時(shí)間耗費(fèi)。如果W(n)表示算法最壞情況時(shí)間復(fù)雜度，則

W(n)=max{t(x)}第23頁(yè)，共25頁(yè)，2023年，2月20日，星期三2023/2/28242.算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行該算法所需的內(nèi)存空間，記作

S(