算法設(shè)計(jì)與分析第二講

《算法設(shè)計(jì)與分析第二講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、智能信息處理研究中心（RCIIP）計(jì)算機(jī)算法設(shè)計(jì)與分析潘海為1智能信息處理研究中心（RCIIP）算法的復(fù)雜性?算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源?算法的時(shí)間復(fù)雜性T(n)；?算法的空間復(fù)雜性S(n)。其中n是問題的規(guī)模（輸入大?。?。2智能信息處理研究中心（RCIIP）算法的時(shí)間復(fù)雜性?（1）最壞情況下的時(shí)間復(fù)雜性T(n)=max{T(I)

2、size(I)=n}max?（2）最好情況下的時(shí)間復(fù)雜性T(n)=min{T(I)

3、size(I)=n}min?（3）平均情況下的時(shí)間復(fù)雜性T(n)=?p(I)T(I)avgsize(I)?n其中I是問題的規(guī)模

4、為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。3智能信息處理研究中心（RCIIP）算法的漸近復(fù)雜性?T(n)??,asn??;?(T(n)-t(n))/T(n)?0，asn??;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。?在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。4智能信息處理研究中心（RCIIP）漸近分析的記號(hào)?在下面的討論中，對(duì)所有n，f(n)?0，g(n)?0。?（1）漸近上界記號(hào)OO(g(n))={f(n)

5、存在正常數(shù)c和n使得對(duì)所有n?n有：000?f(n)?cg(n)}?（2）漸近下

6、界記號(hào)??(g(n))={f(n)

7、存在正常數(shù)c和n使得對(duì)所有n?n有：000?cg(n)?f(n)}5智能信息處理研究中心（RCIIP）漸近分析的記號(hào)?（3）非緊上界記號(hào)oo(g(n))={f(n)

8、對(duì)于任何正常數(shù)c>0，存在正數(shù)和n>0使得對(duì)所有n?n有：0?f(n)

9、對(duì)于任何正常數(shù)c>0，存在正數(shù)和n>0使得對(duì)所有n?n有：0?cg(n)

10、o(f(n))智能信息處理研究中心（RCIIP）漸近分析的記號(hào)?（5）緊漸近界記號(hào)??(g(n))={f(n)

11、存在正常數(shù)c,c和n使得對(duì)所有120n?n有：cg(n)?f(n)?cg(n)}012?定理1：?(g(n))=O(g(n))??(g(n))7智能信息處理研究中心（RCIIP）漸近分析記號(hào)在等式和不等式中的意義?f(n)=?(g(n))的確切意義是：f(n)??(g(n))。?一般情況下，等式和不等式中的漸近記號(hào)?(g(n))表示?(g(n))中的某個(gè)函數(shù)。?例如：2n2+3n+1=2n2+?(n)表示2n2+3n+1=2n2+f(n

12、)，其中f(n)是?(n)中某個(gè)函數(shù)。?等式和不等式中漸近記號(hào)O,o,?和?的意義是類似的。8智能信息處理研究中心（RCIIP）漸近分析中函數(shù)比較?f(n)=O(g(n))?a?b;?f(n)=?(g(n))?a?b;?f(n)=?(g(n))?a=b;?f(n)=o(g(n))?ab.9智能信息處理研究中心（RCIIP）漸近分析記號(hào)的若干性質(zhì)?（1）傳遞性：?f(n)=?(g(n))，g(n)=?(h(n))?f(n)=?(h(n))；?f(n)=O(g(n))，g(n)=O(h(n))?f(n)=O(h(

13、n))；?f(n)=?(g(n))，g(n)=?(h(n))?f(n)=?(h(n))；?f(n)=o(g(n))，g(n)=o(h(n))?f(n)=o(h(n))；?f(n)=?(g(n))，g(n)=?(h(n))?f(n)=?(h(n))；10智能信息處理研究中心（RCIIP）漸近分析記號(hào)的若干性質(zhì)?（2）反身性：f(n)=?(f(n))；f(n)=O(f(n))；f(n)=?(f(n)).?（3）對(duì)稱性：f(n)=?(g(n))?g(n)=?(f(n)).?（4）互對(duì)稱性：f(n)=O(g(n))?g(n)=?(f(n))；f(n)=o

14、(g(n))?g(n)=?(f(n))；11智能信息處理研究中心（RCIIP）漸近分析記號(hào)的若干性質(zhì)?（5）算術(shù)運(yùn)算：?O(f(n))+O(g(n))=O(max{f(n),g(n)})；?O(f(n))+O(g(n))=O(f(n)+g(n))；?O(f(n))*O(g(n))=O(f(n)*g(n))；?O(cf(n))=O(f(n))；?g(n)=O(f(n))?O(f(n))+O(g(n))=O(f(n))。12智能信息處理研究中心（RCIIP）漸近分析記號(hào)的若干性質(zhì)?規(guī)則O(f(n))+O(g(n))=O(max{f(n),g(n)})

15、證明：?對(duì)于任意f(n)?O(f(n))，存在正常數(shù)c和自然數(shù)n，使得對(duì)所有n?n，有1111f(n)?cf(n)。11?類似地，對(duì)于任