解決問題：比較演算法
演算法是解決特定問題的分步指令集，重要的是要理解同一個問題可以用多種演算法來解決。
規範的這一部分關注的是用於從針對同一問題的一組演算法中選擇最適合給定問題集的演算法的標準。
換句話說，如何衡量給定演算法的效率，以便將其與解決同一問題的不同演算法進行比較？
一個非常常見的問題是在一組專案中搜索一個專案。這可能是在非常大的資料庫中搜索一個人的姓名。
下面說明了解決此問題的一種演算法
[此處將跟隨線性搜尋流程圖的影像]
[此處將跟隨 Python 實現的連結]
下面說明了另一種解決同一問題的演算法。
[此處將新增二進位制搜尋流程圖的影像]
[此處將新增 Python 實現的連結]
兩種演算法都解決了同一個問題。應該選擇哪一個演算法來作為程式編碼以解決問題？
為了決定選擇哪種演算法而不是另一種演算法，它們在效率方面進行了比較：找到解決方案所需的時間以及在此過程中消耗的資源。考慮不同汽車之間的選擇，你可能會考慮從一個目的地到另一個目的地的行駛速度和旅途中的燃油消耗量。
也就是說，演算法在終止並得出正確解決方案之前將佔用多少（記憶體）空間。
為了識別空間效率，我們需要檢視演算法執行時使用的結構化資料量。在考慮空間效率時，目標是利用佔用記憶體最少的結構化資料。
示例
- 用型別為real的變數填充列表在空間效率方面會很低，當很明顯只需要整數（整數）來解決問題時。
- 用長度為 1000 初始化陣列在空間效率方面會很低，當很明顯要儲存的最大元素為 100 時。
這是演算法終止並得出正確解決方案所需的時間。
任何時間度量都將取決於其他因素，例如
- 用於實現演算法的特定版本和型別的程式語言；
- 實現將執行的硬體規格；
- 當然還有演算法的輸入，例如，搜尋非常大的集合將比搜尋較小的集合花費更長的時間，並且搜尋不存在於集合中的專案將比搜尋存在於給定集合中的專案花費更長的時間。
顯然，在比較不同演算法時，將這些依賴關係降至最低非常重要。所使用的程式語言和硬體都會隨著時間的推移而發生變化。因此，人們普遍認為任何比較都不應將這些因素考慮在內。
這使我們只剩下輸入的大小作為我們希望在考慮演算法終止並得出正確答案所需的時間時允許的唯一依賴項。
換句話說，我們想要找到一個函式 f(n)，其中 n 是輸入的大小，例如要搜尋的列表的長度。該函式使用演算法終止所需的計算步驟數。
為了消除依賴性，在計算效率時，只考慮以下步驟
- 記憶體訪問 - 也就是說任何記憶體查詢，例如呼叫變數
- 分配
- 任何算術表示式
- 比較
|
與演算法比較相關的疑問 考慮以下演算法 number1 <- 輸入 number2 <- 輸入 sum1 <- number1 + number2 number3 <- 輸入 sum2 <- sum1 + number3 計算演算法中的計算步驟數
回答 7
回答
number2 <- 輸入 number3 <- 輸入 sum <- number1 + number2 + number3
|