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

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