算法引論及簡單算法

算法引論及簡單算法第一頁，共三十七頁，2022年，8月28日2注意算法是程序設(shè)計的靈魂第二頁，共三十七頁，2022年，8月28日3與數(shù)據(jù)結(jié)構(gòu)的區(qū)別：考慮問題的角度：數(shù)據(jù)結(jié)構(gòu)關(guān)心不同的數(shù)據(jù)結(jié)構(gòu)在解題中的作用和效率；算法關(guān)心不同設(shè)計技術(shù)的適用性和效率?？紤]問題的高度：數(shù)據(jù)結(jié)構(gòu)關(guān)心的是解具體問題，算法不僅如此，它提供一種解決問題的通用方法。與其他課程的關(guān)系高級程序設(shè)計語言（C語言，等）數(shù)據(jù)結(jié)構(gòu)算法設(shè)計與分析系統(tǒng)的設(shè)計與實現(xiàn)第三頁，共三十七頁，2022年，8月28日4主要內(nèi)容目標(biāo)：了解算法分析的基本含義。掌握查找算法、排序算法、遞推算法等算法理念。提綱補1.1算法分析補1.2查找算法補1.3排序算法補1.4遞推算法第四頁，共三十七頁，2022年，8月28日5補1.1算法分析前面的課程內(nèi)容以C語言語法為主本補充章介紹一些基本算法大家在編寫程序的時候，“八仙過海，各顯神通”，解決同一個問題，可以使用各種方法。算法之間存在著“優(yōu)劣”之分第五頁，共三十七頁，2022年，8月28日6補1.1算法分析1、算法分析的目的

通過對算法分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好算法，改進(jìn)差算法，避免無益的人力和物力浪費。第六頁，共三十七頁，2022年，8月28日7補1.1算法分析2、算法分析的含義算法分析是一種分析技術(shù)，它以獨立于具體的硬件平臺、編譯器和編程語言的方式，來描述算法的執(zhí)行行為，即它關(guān)心的是算法，而不是程序。算法分析是一種測量算法的性能的方法，它不關(guān)心精確的細(xì)節(jié)，如在算法的某次運行中總共執(zhí)行了多少條機器指令，而是想要一個大致的估計，即隨著輸入數(shù)據(jù)規(guī)模的增大，算法所需工作量以何種速度遞增。（關(guān)心變化趨勢）第七頁，共三十七頁，2022年，8月28日8補1.1算法分析3、算法復(fù)雜性時間復(fù)雜性和空間復(fù)雜性第八頁，共三十七頁，2022年，8月28日9補1.1算法分析1.有些計算機需要用戶提供程序運行時間的上限，一旦達(dá)到這個上限，程序?qū)⒈粡娭平Y(jié)束。2.正在開發(fā)的程序可能需要提供一個滿意的實時響應(yīng)。為什么要考慮時間復(fù)雜性？第九頁，共三十七頁，2022年，8月28日101.多用戶系統(tǒng)中運行時，需指明分配給該程序的內(nèi)存大小。2.可提前知道是否有足夠可用的內(nèi)存來運行該程序。3.一個問題可能有若干個內(nèi)存需求各不相同的解決方案，從中擇取。4.利用空間復(fù)雜性來估算一個程序所能解決問題的最大規(guī)模?？紤]程序的空間復(fù)雜性的理由：補1.1算法分析第十頁，共三十七頁，2022年，8月28日114.

如何進(jìn)行算法分析？事前分析：就算法本身，通過對其執(zhí)行性能的理論分析，得出關(guān)于算法特性——時間和空間的一個特征函數(shù)（Ο）——與計算機軟硬件沒有直接關(guān)系。事后測試：將算法編制成程序后放到計算機上運行，收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進(jìn)行分析判斷——直接與物理實現(xiàn)有關(guān)。補1.1算法分析第十一頁，共三十七頁，2022年，8月28日121）事前分析目的：試圖得出關(guān)于算法執(zhí)行特性的一種形式描述，以“理論上”衡量算法“好壞”。如何給出反映算法執(zhí)行特性的描述？最直接方法：統(tǒng)計算法中各種運算的執(zhí)行情況：

運用了哪些運算每種運算被執(zhí)行的次數(shù)該種運算執(zhí)行一次所花費的時間

算法的執(zhí)行時間=∑Fi*ti補1.1

算法分析第十二頁，共三十七頁，2022年，8月28日13估算執(zhí)行時間的方法

選擇一種或多種（如加、乘和比較等），然后確定這種（些）操作分別執(zhí)行了多少次。令n代表程序?qū)嵗卣鳎瑒t執(zhí)行時間計算公式為：TP（n）=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+···c1、c2、c3、c4分別表示一次加、減、乘、除操作所需的時間。函數(shù)ADD(n)、SUB(n)、MUL(n)、DIV(n)分別表示程序P中，所使用的加、減、乘、除操作的次數(shù)。這種方法是否成功取決于識別關(guān)鍵操作的能力，這些關(guān)鍵操作對時間復(fù)雜性的影響最大。一條語句在整個程序運行時實際執(zhí)行時間=

頻率計數(shù)*每執(zhí)行一次該語句所需的時間補1.1

算法分析第十三頁，共三十七頁，2022年，8月28日14頻率計數(shù)：算法中語句或運算的執(zhí)行次數(shù)。

例：

x=x+yfor(i=1;i<=n;i++)for(i=1;i<=n;i++)x=x+y;for(j=1;j<=n;j++)x=x+y;(a)(b)(c)

分析：

(a)：x=x+y執(zhí)行了1次

(b)：x=x+y執(zhí)行了n次

(c)：x=x+y執(zhí)行了n2次注：在事前分析中，只限于確定與所使用機器及其他環(huán)境因素?zé)o關(guān)的頻率計數(shù)，依此建立一種理論上分析模型。補1.1

算法分析第十四頁，共三十七頁，2022年，8月28日15數(shù)量級語句的數(shù)量級：語句的執(zhí)行頻率。例：1，n，n2

算法的數(shù)量級：算法包含所有語句的執(zhí)行頻率之和。算法的數(shù)量級從本質(zhì)上反映了一個算法的執(zhí)行特性。例：求解同一問題的三個算法分別具有n,n2,n3數(shù)量級。若n=10，則可能的執(zhí)行時間將分別是10，100，1000個單位時間——與環(huán)境因素?zé)o關(guān)。補1.1

算法分析第十五頁，共三十七頁，2022年，8月28日16補1.1

算法分析5、算法復(fù)雜性的等級常量階時間復(fù)雜度為O(1)算法運行時間不隨著問題的規(guī)模而變化如：簡單的賦值語句，x=y;算術(shù)運算，x=y*5+z%3;固定次數(shù)的循環(huán)語句等for(i=0;i<10;i++)for(j=0;j<20;j++)a[i][j]=0;第十六頁，共三十七頁，2022年，8月28日17補1.1算法分析線性階時間復(fù)雜度為O(n)算法運行時間隨著問題的規(guī)模而成線性變化for(i=0;i<n;i++)sum=sun+i;算法執(zhí)行了多少次運算？i=0;執(zhí)行了1次i<n;執(zhí)行了n+1次i++；執(zhí)行了n次sum=sun+i;執(zhí)行了n次共執(zhí)行了3n+2次運算時間復(fù)雜度就是O（3n+2）實際上，算法的時間復(fù)雜度并不精確計算基本操作的執(zhí)行次數(shù)，它主要考慮問題規(guī)模的增長率。O（n）第十七頁，共三十七頁，2022年，8月28日18補1.1算法分析平方階時間復(fù)雜度為O(n2)算法運行時間隨著問題的規(guī)模而成平方變化for(i=0;i<n;i++){

for(j=0;j<n;j++) { sum=sun+a[i][j];//執(zhí)行n2次

} printf(“%dn”,sum);//執(zhí)行n次}時間復(fù)雜度就是O（n2）第十八頁，共三十七頁，2022年，8月28日19補1.1

算法分析多項式階時間復(fù)雜度為O(nd)d為固定常數(shù)算法運行時間隨著問題的規(guī)模而成d次多項式階變化對數(shù)階O(logn)指數(shù)階O(log2n)階乘階O(n!)………若T(n)=adnd+…+a1n+a0是一個d次多項式，則有T(n)=O(nd)第十九頁，共三十七頁，2022年，8月28日205、算法分類（計算時間）多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。

常見的多項式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法

常見的指數(shù)時間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)

說明：當(dāng)n取值較大時，指數(shù)時間算法和多項式時間算法在計算時間上非常懸殊。補1.1

算法分析第二十頁，共三十七頁，2022年，8月28日21

計算時間的數(shù)量級對算法有效性的影響數(shù)量級的大小對算法的有效性有決定性的影響。例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數(shù)量級分別是n2和nlogn。則：

n=1024：分別需要1048576和10240次運算。

n=2048：分別需要4194304和22528次運算。分析：在n加倍的情況下，一個Ο(n2)的算法計算時間增長4倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。補1.1

算法分析第二十一頁，共三十七頁，2022年，8月28日22典型的計算時間函數(shù)曲線結(jié)論：在順序處理機上擴大所處理問題的規(guī)模，最有效的途徑是降低算法計算復(fù)雜度的數(shù)量級，而不是（僅僅依靠）提高計算機的速度。補1.1

算法分析第二十二頁，共三十七頁，2022年，8月28日23補1.2查找算法所謂查找（search），即根據(jù)給定的某個值，在一組數(shù)據(jù)（如一個數(shù)組）中，確定有沒有出現(xiàn)相同值得數(shù)據(jù)元素。查找是非常實用的算法。如，查找字典。問題描述，令b表示被查找的數(shù)組，n表示數(shù)組元素的個數(shù)，x表示被查找的目標(biāo)。問題是“數(shù)據(jù)x是否出現(xiàn)在數(shù)組b當(dāng)中？”第二十三頁，共三十七頁，2022年，8月28日24補1.2查找算法1、順序查找方法基本思路：從數(shù)組b的第一個元素開始，逐個地與x進(jìn)行比較，一直到查找成功或者所有的數(shù)組元素都已經(jīng)處理完畢。參考程序：intsearch(intb[],intn,intx){intk;for(k=0;(k<n)&&(b[k]!=x);k++)if(k<n)return(k);elsereturn(-1);}算法的復(fù)雜度為O(n)第二十四頁，共三十七頁，2022年，8月28日25補1.2查找算法2、折半查找方法(對于有序數(shù)組)參考程序：intsearch(intb[],intn,intx){intL,R,mid;L=0;R=n-1;while(L<=R){mid=(L+R)/2;if(x==b[mid])return(mid); elseif(x<b[mid])R=mid-1;elseL=mid+1;}return(-1);}算法的復(fù)雜度為O(lnN)第二十五頁，共三十七頁，2022年，8月28日26補1.3

排序算法所謂排序（sort），就是將一個任意的數(shù)據(jù)元素的序列，重新排列成一個具有某種順序的序列。排序是非常實用的算法。如，成績排名等。問題描述，令a表示待排序的數(shù)組，n表示數(shù)組元素的個數(shù)，在排序之前，數(shù)組中元素是隨機的，而在排序之后，這些數(shù)據(jù)按照一定的規(guī)律存放。第二十六頁，共三十七頁，2022年，8月28日27補1.3

排序算法冒泡法基本思路：其原理為從a[0]開始，依次將其和后面的元素比較,若a[0]>a[i]，則交換它們，一直比較到a[n]。同理對a[1],a[2],...a[n-1]處理，即完成排序。

voidbubble(int*a,intn)/*定義兩個參數(shù)：數(shù)組首地址與數(shù)組大小*/{inti,j,temp;

for(i=0;i<n-1;i++)for(j=i+1;j<n;j++)/*注意循環(huán)的上下限*/if(a[i]>a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}第二十七頁，共三十七頁，2022年，8月28日28補1.3

排序算法選擇法

基本思路：選擇法循環(huán)過程與冒泡法一致，它還定義了記號k=i,然后依次把a[k]同后面元素比較，若a[k]>a[j],則使k=j.最后看看k=i是否還成立，不成立則交換a[k],a[i],這樣就比冒泡法省下許多無用的交換，提高了效率。voidchoise(int*a,intn){ inti,j,k,temp; for(i=0;i<n-1;i++){ k=i;/*給記號賦值*/ for(j=i+1;j<n;j++) if(a[k]>a[j])k=j;/*是k總是指向最小元素*/ if(i!=k){/*當(dāng)k!=i是才交換，否則a[i]即為最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } }}第二十八頁，共三十七頁，2022年，8月28日29補1.4

遞推算法遞推（RecursiveAlgorithm），即從某個一直得初始條件出發(fā)，根據(jù)這個已知的事實，并按照一定規(guī)律推斷出下一個事實。然后再從這個新的已知的事實出發(fā)，向下再推斷一個事實。遞推是計算機數(shù)值計算的一個重要方法，可以將復(fù)雜的運算簡化為若干個重復(fù)的簡單運算，從而發(fā)揮計算機長于重復(fù)處理的特點。其實質(zhì)與差分方程類似，著名的例子為Fibonacci數(shù)列。第二十九頁，共三十七頁，2022年，8月28日30補1.4

遞推算法例：猴子吃桃有一只小猴子，有一天摘了一堆桃子，當(dāng)天吃掉了一半，后來覺得不過癮，就又多吃了一只。第二天，小猴子又將剩下的桃子吃掉了一半，并多吃了一個。以后每天都吃了前一天剩下的一半零一個。到了第十天的時候，發(fā)現(xiàn)只剩下一只桃子了。請問小猴子第一天一共摘了多少桃子？第三十頁，共三十七頁，2022年，8月28日31補1.4

遞推算法解題思路T10=T9-T9/2-1即T9=(T10+1)*2T8=(T9+1)*2T7=(T8+1)*2……

……T1=(T2+1)*2定義A為桃子的個數(shù)，第10天為1個，第9天為4個，第8天為10個。。。。。#include<stdio.h>voidmain(){intA,i;A=1;for(i=9;i>=1;i--)A=(A+1)*2

pintf("小猴子第一天共摘了%d個桃子.\n"，A);}第三十一頁，共三十七頁，2022年，8月28日32補1.4

遞推算法例：猴子分桃1979年李政道去中國科技大學(xué)訪問，出了一道題目。5只猴子摘了一堆桃子，等第二天再來分。夜里一只猴子偷偷爬起來，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己應(yīng)得到的一份，然后回家了。過了會兒，第二只猴子也爬了起來，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己應(yīng)得到的一份。第三、四、五只猴子都是這樣，吃掉了一只桃子后，正好把剩下的桃子每次都能分成5份。請問最初至少有多少個桃子？每只猴子夜里起床后看到多少只桃子？第三十二頁，共三十七頁，2022年，8月28日33補1.4

遞推算法解題思路定義peach[i]（1≤i≤5）表示第i只猴子看到的桃子數(shù)。peach[2]=(peach[1]-1)*4/5peach[i]=(peach[i-1]-1)*4/5（2≤i≤5）

如果知道了peach[1]或者peach[5]中的任意一個，都可以遞推出來每只猴子看到的桃子個數(shù)?？上Р恢腊?。第三十三頁，共三十七頁，2022年，8月28日34補1.4

遞推算法解題思路但是我們知道：peach[1]%5=1；peach[2]%