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