算法設(shè)計與分析 課件 1.2.3-算法分析準(zhǔn)則 - 時間復(fù)雜度 - 漸近分析及符號表示

算法設(shè)計與分析算法分析-時間復(fù)雜度-漸近分析及符號表示信息工程大學(xué)國家級實驗教學(xué)示范中心計算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版計數(shù)法，即統(tǒng)計算法執(zhí)行的基本操作次數(shù)步驟： 1.確定基本操作； 2.按相關(guān)公式建立關(guān)于n的表達(dá)式； 3.化簡表達(dá)式。

什么是漸近分析漸近分析符號一二算法分析中的Bigidea漸近分析在問題規(guī)模足夠大后，時間復(fù)雜度的增長趨勢。主流（忽略細(xì)節(jié)）+長遠(yuǎn)（規(guī)模足夠大）時間復(fù)雜度即漸近時間復(fù)雜度(AsymptoticTimeComplexity)約翰·霍普克羅夫特（JohnEdwardHopcroft）符號：O定義：設(shè)f(n)和g(n)是定義在自然數(shù)集N上的函數(shù)，若存在常數(shù)C>0和正整數(shù)n0，使得對所有的n>n0，若f(n)≤C*g(n)，則稱f(n)的階不高于g(n)的階且g(n)是f(n)的一個上界，記作f(n)=O(g(n))。即表明:f(n)的增長最多像g(n)的增長那樣快。f(n)cg(n)n0運行時間輸入規(guī)模符號：

定義：若f(n)=

(g(n))且g(n)=

(f(n))，則稱f(n)和g(n)是同階的，且記作：f(n)=

(g(n))或g(n)=

(f(n))。即，表明:f(n)的增長和g(n)的增長同樣快，稱

(g(n))是f(n)的準(zhǔn)確界。（C>0,為常數(shù)）符號：

定義：若f(n)≥Cg(n),則稱f(n)的階不低于g(n)的階，并記作f(n)=

(g(n))，即，表明:f(n)的增長至少像g(n)那樣快，稱

(g(n))是f(n)的下界。符號：o定義：如果對于任意給定的ε≥0，都存在非負(fù)整數(shù)n0，使得當(dāng)N≥n0時有f(N)<εg(N)，則稱函數(shù)f(N)當(dāng)N充分大時，比g(N)低階，記為f(N)=o(g(N))。o記為緊上界符號。符號：ω定義：若g(N)=o(f(N)),即當(dāng)N充分大時，f(N)的階比g(N)高，則記f(N)=ω(g(N))。ω記為緊下界符號。測試單選題：在時間復(fù)雜度的結(jié)果表示中，表示下界的符號為（）；表示同階的符號為（）；表示上界的符號為（）；表示緊上界的符號為（）；表示緊下界的符號為（）。A：O B：

C：

D：o E：ω函數(shù)階關(guān)系證明證明兩個函數(shù)滿足同階、低階或高階關(guān)系，有以下方法：1.按照階的定義，找到合適的常數(shù)c和n0。2.使用求極限方法，如洛必達(dá)法則。幾點說明不能寫O(g(n))=f(n)或

(g(n))=f(n)。在函數(shù)中，低階項不影響函數(shù)的階。時間復(fù)雜度表達(dá)式中選擇階最高的項，去掉系數(shù)，加上O，即可得到漸進(jìn)時間復(fù)雜度。當(dāng)改進(jìn)算法時，首先降低算法復(fù)雜度的階，其次再考慮減小項的系數(shù)，再減少低階項。幾個例子例1：f(n)=2022f(n)=O(1)例2：f(n)=n+2log3nf(n)=O(n)