- 留學生輔導網(wǎng)
- 關(guān)于我們 網(wǎng)站地圖 免責聲明
搜索
導航
發(fā)布時間：2023-11-02 13:55
通常，算法的效率或運行時間被表述為輸入長度與步驟數(shù)(時間復雜度)或存儲位置(空間復雜度)之間的函數(shù)關(guān)系。算法分析是更廣泛的計算復雜性理論的重要組成部分，它為解決給定計算問題的任何算法所需的資源提供理論估算。這些估算為尋找高效算法提供了合理的方向。在算法的理論分析中，通常從漸進的意義上估計算法的復雜性，即估計任意大輸入的復雜性函數(shù)。為此，我們使用了大 O 符號、大歐米茄符號和大θ符號。
經(jīng)驗法則可以通過計算程序的嵌套循環(huán)來分析簡單程序。對 n 個項目的單個循環(huán)產(chǎn)生 f( n ) = n。循環(huán)中的循環(huán)產(chǎn)生 f( n ) = n3。
經(jīng)驗法則：對于一系列連續(xù)的 for 循環(huán)，其中最慢的循環(huán)決定了程序的漸近行為。兩個嵌套循環(huán)后接一個單循環(huán)，其漸近行為與單獨的嵌套循環(huán)相同，因為嵌套循環(huán)支配著簡單循環(huán)。
一、分析類型
算法復雜度可以是最佳、平均或最壞情況分析。算法分析可以使用大 O 符號表示。給定算法的最佳、最差和平均情況分別表示資源使用的最少、最多和平均值。大 O 符號簡化了算法的比較。
1.最佳情況
計算機科學中的最佳情況性能，用于描述算法在最佳條件下的行為。最佳情況性能的一個例子是嘗試使用某種排序算法對已經(jīng)排序的列表進行排序。例如：[1,2,3] --> [1,2,3] 。
2.平均情況
使用解決問題的平均最優(yōu)條件來衡量平均情況性能。例如，一個既不是最佳條件也不是最差條件的列表，你希望它按一定順序排序。例如 [2,1,5,3] --> [1,2,3,5] 或 [ 2,1,5,3] --> [5,3,2,1] 。
3.最差情況
最壞情況性能用于分析算法在最壞輸入情況下的行為，以及解決問題的最小可能性。它決定了算法在給定輸入條件下何時表現(xiàn)最差。最差情況性能的一個例子是，一個已經(jīng)按升序排序的姓名列表，你想按降序排序。例如：[Abby, Bill, Catherine] --> [Catherine, Bill, Abby]。
二、遞歸復雜性
dionyziz
現(xiàn)在讓我們來看看遞歸函數(shù)。遞歸函數(shù)是一個調(diào)用自身的函數(shù)。我們能分析一下它的復雜性嗎?下面這個函數(shù)是用 Python 寫的，用來計算給定數(shù)字的階乘。正整數(shù)的階乘是將它與之前所有的正整數(shù)相乘得到的。例如，5 的階乘是 5 * 4 * 3 * 2 * 1。我們將其表示為 "5!"，并將其發(fā)音為 "5 的階乘"。
1.def factorial( n )：
如果 n == 1：
返回 1 4.
4. 返回 n * factorial( n - 1 )
讓我們分析一下這個函數(shù)的復雜性。這個函數(shù)中沒有任何循環(huán)，但它的復雜度也不是恒定的。要想知道它的復雜度，我們需要再次計算指令。很明顯，如果我們給這個函數(shù)傳遞 n，它就會執(zhí)行 n 次。如果你對此不確定，現(xiàn)在就 "手動 "運行 n = 5，以驗證它是否真的有效。例如，對于 n = 5，它會執(zhí)行 5 次，因為每次調(diào)用都會將 n 減少 1。因此，我們可以看到這個函數(shù)是 Θ( n )。
如果你對這一事實不確定，請記住，你總是可以通過計算指令來找到精確的復雜度。如果你愿意，現(xiàn)在可以嘗試計算這個函數(shù)執(zhí)行的實際指令，找到一個函數(shù) f( n )，看看它確實是線性的(記住，線性意味著 Θ( n ))。
如果你對此還有疑問,或者有更多關(guān)于學業(yè)輔導方面需求的話,可以添加微信號：hmkt131聯(lián)系海馬課堂的Joye老師哦。
相關(guān)熱詞搜索： 留學作業(yè)輔導 新加坡作業(yè)輔導
