算法引論及簡單算法第1頁，課件共37頁，創作于2023年2月2注意算法是程序設計的靈魂第2頁，課件共37頁，創作于2023年2月3與數據結構的區別：考慮問題的角度：數據結構關心不同的數據結構在解題中的作用和效率；算法關心不同設計技術的適用性和效率?？紤]問題的高度：數據結構關心的是解具體問題，算法不僅如此，它提供一種解決問題的通用方法。與其他課程的關系高級程序設計語言（C語言，等）數據結構算法設計與分析系統的設計與實現第3頁，課件共37頁，創作于2023年2月4主要內容目標：了解算法分析的基本含義。掌握查找算法、排序算法、遞推算法等算法理念。提綱補1.1算法分析補1.2查找算法補1.3排序算法補1.4遞推算法第4頁，課件共37頁，創作于2023年2月5補1.1算法分析前面的課程內容以C語言語法為主本補充章介紹一些基本算法大家在編寫程序的時候，“八仙過海，各顯神通”，解決同一個問題，可以使用各種方法。算法之間存在著“優劣”之分第5頁，課件共37頁，創作于2023年2月6補1.1算法分析1、算法分析的目的

通過對算法分析，在把算法變成程序實際運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好算法，改進差算法，避免無益的人力和物力浪費。第6頁，課件共37頁，創作于2023年2月7補1.1算法分析2、算法分析的含義算法分析是一種分析技術，它以獨立于具體的硬件平臺、編譯器和編程語言的方式，來描述算法的執行行為，即它關心的是算法，而不是程序。算法分析是一種測量算法的性能的方法，它不關心精確的細節，如在算法的某次運行中總共執行了多少條機器指令，而是想要一個大致的估計，即隨著輸入數據規模的增大，算法所需工作量以何種速度遞增。（關心變化趨勢）第7頁，課件共37頁，創作于2023年2月8補1.1算法分析3、算法復雜性時間復雜性和空間復雜性第8頁，課件共37頁，創作于2023年2月9補1.1算法分析1.有些計算機需要用戶提供程序運行時間的上限，一旦達到這個上限，程序將被強制結束。2.正在開發的程序可能需要提供一個滿意的實時響應。為什么要考慮時間復雜性？第9頁，課件共37頁，創作于2023年2月101.多用戶系統中運行時，需指明分配給該程序的內存大小。2.可提前知道是否有足夠可用的內存來運行該程序。3.一個問題可能有若干個內存需求各不相同的解決方案，從中擇取。4.利用空間復雜性來估算一個程序所能解決問題的最大規模?？紤]程序的空間復雜性的理由：補1.1

算法分析第10頁，課件共37頁，創作于2023年2月114.

如何進行算法分析？事前分析：就算法本身，通過對其執行性能的理論分析，得出關于算法特性——時間和空間的一個特征函數（Ο）——與計算機軟硬件沒有直接關系。事后測試：將算法編制成程序后放到計算機上運行，收集其執行時間和空間占用等統計資料，進行分析判斷——直接與物理實現有關。補1.1算法分析第11頁，課件共37頁，創作于2023年2月121）事前分析目的：試圖得出關于算法執行特性的一種形式描述，以“理論上”衡量算法“好壞”。如何給出反映算法執行特性的描述？最直接方法：統計算法中各種運算的執行情況：

運用了哪些運算每種運算被執行的次數該種運算執行一次所花費的時間

算法的執行時間=∑Fi*ti補1.1

算法分析第12頁，課件共37頁，創作于2023年2月13估算執行時間的方法

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

頻率計數*每執行一次該語句所需的時間補1.1

算法分析第13頁，課件共37頁，創作于2023年2月14頻率計數：算法中語句或運算的執行次數。

例：

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執行了1次

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

(c)：x=x+y執行了n2次注：在事前分析中，只限于確定與所使用機器及其他環境因素無關的頻率計數，依此建立一種理論上分析模型。補1.1算法分析第14頁，課件共37頁，創作于2023年2月15數量級語句的數量級：語句的執行頻率。例：1，n，n2

算法的數量級：算法包含所有語句的執行頻率之和。算法的數量級從本質上反映了一個算法的執行特性。例：求解同一問題的三個算法分別具有n,n2,n3數量級。若n=10，則可能的執行時間將分別是10，100，1000個單位時間——與環境因素無關。補1.1算法分析第15頁，課件共37頁，創作于2023年2月16補1.1算法分析5、算法復雜性的等級常量階時間復雜度為O(1)算法運行時間不隨著問題的規模而變化如：簡單的賦值語句，x=y;算術運算，x=y*5+z%3;固定次數的循環語句等for(i=0;i<10;i++)for(j=0;j<20;j++)a[i][j]=0;第16頁，課件共37頁，創作于2023年2月17補1.1算法分析線性階時間復雜度為O(n)算法運行時間隨著問題的規模而成線性變化for(i=0;i<n;i++)sum=sun+i;算法執行了多少次運算？i=0;執行了1次i<n;執行了n+1次i++；執行了n次sum=sun+i;執行了n次共執行了3n+2次運算時間復雜度就是O（3n+2）實際上，算法的時間復雜度并不精確計算基本操作的執行次數，它主要考慮問題規模的增長率。O（n）第17頁，課件共37頁，創作于2023年2月18補1.1

算法分析平方階時間復雜度為O(n2)算法運行時間隨著問題的規模而成平方變化for(i=0;i<n;i++){

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

} printf(“%dn”,sum);//執行n次}時間復雜度就是O（n2）第18頁，課件共37頁，創作于2023年2月19補1.1

算法分析多項式階時間復雜度為O(nd)d為固定常數算法運行時間隨著問題的規模而成d次多項式階變化對數階O(logn)指數階O(log2n)階乘階O(n!)………若T(n)=adnd+…+a1n+a0是一個d次多項式，則有T(n)=O(nd)第19頁，課件共37頁，創作于2023年2月205、算法分類（計算時間）多項式時間算法：可用多項式（函數）對其計算時間限界的算法。

常見的多項式限界函數有：

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

常見的指數時間限界函數：

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

說明：當n取值較大時，指數時間算法和多項式時間算法在計算時間上非常懸殊。補1.1算法分析第20頁，課件共37頁，創作于2023年2月21

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

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

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

算法分析第21頁，課件共37頁，創作于2023年2月22典型的計算時間函數曲線結論：在順序處理機上擴大所處理問題的規模，最有效的途徑是降低算法計算復雜度的數量級，而不是（僅僅依靠）提高計算機的速度。補1.1

算法分析第22頁，課件共37頁，創作于2023年2月23補1.2查找算法所謂查找（search），即根據給定的某個值，在一組數據（如一個數組）中，確定有沒有出現相同值得數據元素。查找是非常實用的算法。如，查找字典。問題描述，令b表示被查找的數組，n表示數組元素的個數，x表示被查找的目標。問題是“數據x是否出現在數組b當中？”第23頁，課件共37頁，創作于2023年2月24補1.2查找算法1、順序查找方法基本思路：從數組b的第一個元素開始，逐個地與x進行比較，一直到查找成功或者所有的數組元素都已經處理完畢。參考程序：intsearch(intb[],intn,intx){intk;for(k=0;(k<n)&&(b[k]!=x);k++)if(k<n)return(k);elsereturn(-1);}算法的復雜度為O(n)第24頁，課件共37頁，創作于2023年2月25補1.2查找算法2、折半查找方法(對于有序數組)參考程序：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);}算法的復雜度為O(lnN)第25頁，課件共37頁，創作于2023年2月26補1.3

排序算法所謂排序（sort），就是將一個任意的數據元素的序列，重新排列成一個具有某種順序的序列。排序是非常實用的算法。如，成績排名等。問題描述，令a表示待排序的數組，n表示數組元素的個數，在排序之前，數組中元素是隨機的，而在排序之后，這些數據按照一定的規律存放。第26頁，課件共37頁，創作于2023年2月27補1.3

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

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

for(i=0;i<n-1;i++)for(j=i+1;j<n;j++)/*注意循環的上下限*/if(a[i]>a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}第27頁，課件共37頁，創作于2023年2月28補1.3

排序算法選擇法

基本思路：選擇法循環過程與冒泡法一致，它還定義了記號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){/*當k!=i是才交換，否則a[i]即為最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } }}第28頁，課件共37頁，創作于2023年2月29補1.4

遞推算法遞推（RecursiveAlgorithm），即從某個一直得初始條件出發，根據這個已知的事實，并按照一定規律推斷出下一個事實。然后再從這個新的已知的事實出發，向下再推斷一個事實。遞推是計算機數值計算的一個重要方法，可以將復雜的運算簡化為若干個重復的簡單運算，從而發揮計算機長于重復處理的特點。其實質與差分方程類似，著名的例子為Fibonacci數列。第29頁，課件共37頁，創作于2023年2月30補1.4

遞推算法例：猴子吃桃有一只小猴子，有一天摘了一堆桃子，當天吃掉了一半，后來覺得不過癮，就又多吃了一只。第二天，小猴子又將剩下的桃子吃掉了一半，并多吃了一個。以后每天都吃了前一天剩下的一半零一個。到了第十天的時候，發現只剩下一只桃子了。請問小猴子第一天一共摘了多少桃子？第30頁，課件共37頁，創作于2023年2月31補1.4

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

……T1=(T2+1)*2定義A為桃子的個數，第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);}第31頁，課件共37頁，創作于2023年2月32補1.4

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

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

如果知道了peach[1]或者peach[5]中的任意一個，都可以遞推出來每只猴子看到的桃子個數?？上Р恢腊　５?3頁，課件共37頁，創作于2023年2月34補1.4

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