數(shù)據(jù)結(jié)構(gòu)與算法(Java描述)2、算法的設(shè)計(jì)目標(biāo)與性能指標(biāo)

1、分析：執(zhí)行次數(shù)為2f(n)=n;f(n)=log2n所以T(n)=O(log2n)數(shù)據(jù)結(jié)構(gòu)與算法(Java描述)-2、算法的設(shè)計(jì)目標(biāo)與性能指標(biāo)一、算法的設(shè)計(jì)目標(biāo)1、正確性：滿足具體問題的解，基本目標(biāo)。2、可讀性：有利于人去理解算法。3、健壯性：輸入非法數(shù)據(jù)，能適當(dāng)做出處理，不產(chǎn)生莫名其妙的輸出。4、高效性：包括時(shí)間的高效性和空間的高效性。二、算法性能指標(biāo)1、算法的時(shí)間效率也稱為時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了算法執(zhí)行的時(shí)間長短。度量一個(gè)算法在計(jì)算機(jī)上執(zhí)行的時(shí)間通常有兩種方式：、事后統(tǒng)計(jì)法、事前分析法：(常用)編寫算法使用的高級(jí)語言編程產(chǎn)生的機(jī)器語言代碼質(zhì)量機(jī)器指令執(zhí)行速度問題規(guī)模0()函數(shù)：

2、表示算法的時(shí)間效率與算法所處理的數(shù)據(jù)元素個(gè)數(shù)n函數(shù)關(guān)系的最常用函數(shù)是0()函數(shù)。定義：一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=0(f(n),稱0(f(n)為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。當(dāng)算法的時(shí)間復(fù)雜度T(n)與問題規(guī)模n無關(guān)時(shí)，此時(shí)算法的時(shí)間復(fù)雜度T(n)=0(1)。例如：計(jì)算下列算式的前N項(xiàng)和1-2+3-4+5.+N分析：當(dāng)N為奇數(shù)時(shí)，和為：(N+1)/2當(dāng)N為偶數(shù)時(shí)，和為：-N/2栗子1：設(shè)數(shù)組

3、a和b在前面部分已經(jīng)賦值，求如下兩個(gè)n階矩陣相乘算法的時(shí)間復(fù)雜度for(i=0;in;i+)for(j=0;jn;j+)cij=0;基本語句1for(k=0;kn;k+)cij=cij+aik*bkj;/基本語句2分析：f(n)=c1*n2+c2*n3，所以T(n)=0(n3)栗子2：設(shè)n為如下算法處理的數(shù)據(jù)元素個(gè)數(shù)，求算法時(shí)間復(fù)雜度。for(i=1;i=n;i=i*2)System.out.println(i);2、算法的空間效率也稱為空間復(fù)雜度?？臻g復(fù)雜度是指算法在運(yùn)行期間所需要的內(nèi)存空間的數(shù)量級(jí)。由于大部分算法的空間復(fù)雜度問題并不嚴(yán)重，并且算法的空間復(fù)雜度分析方法和算法的時(shí)間復(fù)雜度分析方

4、法基本相同，所以一般數(shù)據(jù)結(jié)構(gòu)只討論算法的時(shí)間復(fù)雜度，不討論算法的空間復(fù)雜度。栗子1分析如下算法的空間復(fù)雜度staticvoidreserse(inta,intb)intn=a.length;for(inti=0;in;i+)bi=an-1-i;分析：當(dāng)程序調(diào)用reserse(a,b)函數(shù)時(shí)，要分配的內(nèi)存空間包括：引用a,引用b,局部變量n和局部變量i;因此f(n)=c淇中c為常量。所以該算法的空間復(fù)雜度S(n)=0(1)說明：同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。算法時(shí)間的高效性和空間的高效性通常是矛盾的。所有一般只會(huì)取一個(gè)平衡點(diǎn)。通常我們假設(shè)程序運(yùn)行在內(nèi)存中，且內(nèi)存容量足夠使用，所以更多的討論時(shí)間復(fù)雜度。三、小結(jié)算法的時(shí)間復(fù)雜度和兩個(gè)因素有關(guān)：算法中的最大嵌套循環(huán)層數(shù)；最大嵌套循環(huán)結(jié)構(gòu)中每次循環(huán)的次數(shù)。一般來說，具有多項(xiàng)