大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第一章：概論-第三節(jié)-算法的描述與分析

第三節(jié)算法的描述與分析一、算法的描述算法：是對(duì)問(wèn)題求解步驟的一種描述。算法是由若干條指令組成的有窮序列，其中每條指令表示一個(gè)或多個(gè)操作。算法還必須滿(mǎn)足以下五個(gè)準(zhǔn)則：（1）輸入。算法開(kāi)始前必須給算法中用到的變量初始化，一個(gè)算法的輸入可以包含零個(gè)或多個(gè)數(shù)據(jù)。（2）輸出。算法至少有一個(gè)或多個(gè)輸出。（3）有窮性。算法中每一條指令的執(zhí)行次數(shù)都是有限的，而且每一步都在有窮時(shí)間內(nèi)完成，即算法必須在執(zhí)行有限步后結(jié)束。（4）確定性。算法中每一條指令的含義都必須明確，無(wú)二義性。（5）可行性。算法是可行的，即算法中描述的操作都可以通過(guò)有限次的基本運(yùn)算來(lái)實(shí)現(xiàn)。本教材都采用類(lèi)C語(yǔ)言描述算法。真題選解（例題·單選題）算法指的是()A．計(jì)算機(jī)程序B．解決問(wèn)題的計(jì)算方法C．排序算法D．解決問(wèn)題的有限運(yùn)算序列隱藏答案【答案】D【解析】是對(duì)問(wèn)題求解步驟的一種描述。算法是由若干條指令組成的有窮序列，它必須滿(mǎn)足有窮性，即在執(zhí)行有限步驟以后必須結(jié)束。二、算法分析例：百錢(qián)百雞問(wèn)題。100個(gè)錢(qián)買(mǎi)100只雞，其中公雞5錢(qián)1只，母雞3錢(qián)1只，小雞1錢(qián)3只，求公雞、母雞、小雞各買(mǎi)多少只？分析：設(shè)公雞、母雞、小雞分別買(mǎi)a、b、c只，則//函數(shù)返回值為滿(mǎn)足問(wèn)題的解數(shù)，g[]，m[]，s[]分別存放不同解的公雞、母雞和小雞數(shù)intchickenquestion(intg[]，intm[]，ints[]){inta，b，c，k=0；for(a=0；a<=100；a++)for(b=0；b<=100；b++)for(c=0；c<=100；c++)if((a+b+c==100)&&(5*a+3*b+c/3==100)&&(c％3==0)){g[k]=a；m[k]=b；s[k]=c；k=k+1；}returnk；}算法需要執(zhí)行101×101×101約100萬(wàn)次對(duì)上述算法是完全可以改進(jìn)的。intchickenquestion(intg[]，intm[]，ints[]){inta，b，c，k=0；for(a=0；a<=20；a++)for(b=0；b<=33；b++){c=100-a-b；if((5*a+3*b+c/3==100)&&(c％3==0)){g[k]=a；m[k]=b；s[k]=c；k=k+1；}}returnk；}算法需要執(zhí)行21×34=714次。因此，設(shè)計(jì)一個(gè)好的算法，對(duì)提高程序的執(zhí)行效率是至關(guān)重要的。1、評(píng)價(jià)算法的指標(biāo)：（1）算法的正確性，是指對(duì)于一切合法的輸入數(shù)據(jù)，該算法經(jīng)過(guò)有限時(shí)間的執(zhí)行都能得到正確的結(jié)果。（2）執(zhí)行算法所耗費(fèi)的時(shí)間，即時(shí)間復(fù)雜性。（3）執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性。（4）算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。2、算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。記作T（n）=O（f（n））。例：求下面程序段的算法時(shí)間復(fù)雜度。x=0；for(i=2；i<=n；i++)for(j=2；j<=i-l；j++)x=x+1；算法時(shí)間復(fù)雜度只需要求出它關(guān)于n的增長(zhǎng)率或階即可。上述語(yǔ)句x=x+l執(zhí)行次數(shù)關(guān)于n的增長(zhǎng)率為n2，所以該程序段的算法時(shí)間復(fù)雜度為O(n2)。如果一個(gè)算法的執(zhí)行時(shí)間是一個(gè)與"問(wèn)題規(guī)模"無(wú)關(guān)的常數(shù)，即使是一個(gè)較大的常數(shù)，該算法的時(shí)間復(fù)雜度都為常數(shù)階，記作T(n)=O(1)例：y=10000；while(y>0)y--；該程序段的時(shí)間復(fù)雜度就是O(1)時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O（1）、對(duì)數(shù)階O（log2n）、線性階O（n）、線性對(duì)數(shù)階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數(shù)階O（2^n）。真題選解（例題·填空題）1、下面程序段的時(shí)間復(fù)雜度為_(kāi)__________。sum=1；for（i=0；sum<n;i++）sum+=1；隱藏答案【解析】循環(huán)執(zhí)行n次，所以算法的時(shí)間復(fù)雜度為O（n）。【答案】O（n）（例題·填空題）2、估算算法時(shí)間復(fù)雜度時(shí)考慮的問(wèn)題規(guī)模通常是指算法求解問(wèn)題的_________。隱藏答案【答案】輸入量【解析】時(shí)間復(fù)雜度是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。將算法所要求解問(wèn)題的輸入量稱(chēng)為問(wèn)題的規(guī)模。（例題·單選題）3、若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是（）A．問(wèn)題規(guī)模B．語(yǔ)句條數(shù)C．循環(huán)層數(shù)D．函數(shù)數(shù)量隱藏答案【答案】A【解析】時(shí)間復(fù)雜度是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。記作T（n）=O（f（n））。3、空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。4、算法復(fù)雜度：算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱(chēng)算法復(fù)雜度。當(dāng)前講授本