(8.3)-6.3講稿-算法與程序-算法分析

算法與程序計算的效率-算法分析求素數(shù)問題：求100到200之間的素數(shù)方法一：用這個數(shù)除以1到該數(shù)之間的每一個整數(shù)

如果都不能整除，那么該數(shù)為素數(shù)例：求101是否為素數(shù)就讓101除以2到100之間的數(shù)，都不能整除，所以101為素數(shù)求素數(shù)

方案二：我們假設一個數(shù)為x,如果該數(shù)不是一個素數(shù)，那么x一定可以由表達式x=a*b表示，所以當a為2時b可得最大值x/2;當b=2時，a為最大值x/2用x除以2到x/2之間的數(shù)即可

求素數(shù)如果都不能整除，則說明x為素數(shù)求素數(shù)還有沒有繼續(xù)優(yōu)化的空間呢？

方案三：我們發(fā)現(xiàn)a和b一定相等或者一大一小，那么我們只需要除以較小的數(shù)即可，那么較小的數(shù)的范圍是多少呢？

求素數(shù)x如果為偶數(shù)那么x一定不是素數(shù)

當a=b時，a=sqrt(x),所以我們只需除以2到sqrt(x)，判斷能否被整除求素數(shù)怎樣去評價和分析一個算法呢？計算機中最重要的兩種資源時間空間

設計問題求解的算法時，應該多思考，分析算法，不斷尋找更好的解決方案用什么方法來設計算法如何判定一個算法的性能設計的算法需要多少運行時間多少存儲空間算法分析是軟件開發(fā)中必不可少的環(huán)節(jié)。開發(fā)一個軟件時

時間效率關注的是算法運行時所需的計算機時間

空間效率則關注算法需要的額外空間

目前算法分析的主要精力集中在分析時間效率上漸進表示法-分析模型任何一個算法都是由有限個基本運算（算術運算、邏輯運算和賦值操作）組成為了分析方便，將每種運算所需要的時間統(tǒng)一定義為1個單位算法需要的執(zhí)行時間為所有運算個數(shù)之和

執(zhí)行時間與問題規(guī)模n有關，是n的函數(shù)，記作T(n)，T(n)是非負遞增函數(shù)算法的“漸近時間復雜度”（大O表示法）:輸入量n逐漸加大時，時間復雜性的極限情形大O表達式：表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢漸進表示法-分析模型分析模型

這三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關的常數(shù)算法的時間復雜度為常數(shù)階，記作T(n)=O(1)

此類算法的時間復雜度是O(1)Temp=i;i=j;j=temp;

分析模型解：第一條語句執(zhí)行頻度為1次，第二條語句執(zhí)行頻度為n次，第三條語句執(zhí)行頻度為n^2，第四條基本語句sum++的執(zhí)行頻度也是n^2計算T(n)=2n^2+n+1=O(n^2)sum=0；

（一次）

for(i=1;i<=n;i++)

（n次）

for(j=1;j<=n;j++)（n^2次）

sum++；

（n^2次）分析模型

a=0;

b=1;

①

for(i=1;i<=n;i++)②

{

s=a+b;③

b=a;④

a=s;⑤

}

解：語句1的頻度：2,

語句2的頻度：n,

語句3的頻度：n-1,

語句4的頻度：n-1,

語句5的頻度：n-1,