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

算法與程序計(jì)算的效率-算法分析求素?cái)?shù)問(wèn)題：求100到200之間的素?cái)?shù)方法一：用這個(gè)數(shù)除以1到該數(shù)之間的每一個(gè)整數(shù)

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

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

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

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

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

當(dāng)a=b時(shí)，a=sqrt(x),所以我們只需除以2到sqrt(x)，判斷能否被整除求素?cái)?shù)怎樣去評(píng)價(jià)和分析一個(gè)算法呢？計(jì)算機(jī)中最重要的兩種資源時(shí)間空間

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

時(shí)間效率關(guān)注的是算法運(yùn)行時(shí)所需的計(jì)算機(jī)時(shí)間

空間效率則關(guān)注算法需要的額外空間

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

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

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

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

分析模型解：第一條語(yǔ)句執(zhí)行頻度為1次，第二條語(yǔ)句執(zhí)行頻度為n次，第三條語(yǔ)句執(zhí)行頻度為n^2，第四條基本語(yǔ)句sum++的執(zhí)行頻度也是n^2計(jì)算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;⑤

}

解：語(yǔ)句1的頻度：2,

語(yǔ)句2的頻度：n,

語(yǔ)句3的頻度：n-1,

語(yǔ)句4的頻度：n-1,

語(yǔ)句5的頻度：n-1,