演算法分類與範例

演算法的分類有助於選擇最適合特定任務的演算法，使開發人員能夠優化他們的程式碼並獲得更好的效能。在計算機科學中，演算法是一組明確定義的指令，用於解決問題或執行特定任務。這些演算法的效率和有效性對於確定程式的整體效能至關重要。

在本文中，我們將討論兩種常見的演算法分類方法，即基於時間複雜度和基於設計技術。

文法

主要函數的語法在兩種方法的程式碼中使用 -

int main() {
   // Your code here
}

演算法

• 確定要解決的問題。

• 選擇適當的方法來對演算法進行分類。

• 使用選擇的方法在C 中編寫程式碼。

• 編譯並執行程式碼。

• 分析輸出。

時間複雜度是什麼？

時間複雜度是演算法在輸入規模的函數下運行所需時間的量測。它是描述演算法效率和隨著輸入規模增大時演算法的擴展性的一種方式。

時間複雜度通常使用大O符號表示，它給出了演算法的運行時間的上限。例如，時間複雜度為O(1)的演算法意味著運行時間保持恆定，不受輸入大小的影響，而時間複雜度為O(n^2)的演算法則意味著運行時間與輸入大小呈二次增長。了解演算法的時間複雜度在選擇解決問題的正確演算法和比較不同演算法時非常重要。

方法1：根據時間複雜度對演算法進行分類

這種方法涵蓋了根據演算法的時間複雜度進行分類。

這就需要先解讀演算法的持續時間複雜性，然後根據其經過的時間複雜性將其歸類為五個分類之一：O(1)常數時間複雜性，O(log n)對數時間複雜性，O(n)線性時間複雜性，O(n^2)二次時間複雜性，或O(2^n)指數時間複雜性。這種分類揭示了演算法的有效性，並且在選擇演算法時可以考慮輸入資料的大小和期望的完成時間。

Example-1

的中文翻譯為：

範例-1

下面的程式碼展示了線性搜尋演算法的演示，它具有O(n)的線性時間複雜度。此演算法對數組中的元素進行系統檢查，確定是否有任何元素與指定的搜尋元素相符。一旦發現，函數將傳回元素的索引，否則傳回-1，表示元素不在陣列中。主函數透過初始化陣列和搜尋元素，呼叫linearSearch函數，並最終呈現結果來啟動。

<int>#include <iostream>
#include <vector>
#include <algorithm>
// Linear search function with linear time complexity O(n)
int linearSearch(const std::vector<int>& arr, int x) {
    for (size_t i = 0; i < arr.size(); i++) {
        if (arr[i] == x) {
            return static_cast<int>(i);
        }
    }
    return -1;
}
int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int search_element = 5;
    int result = linearSearch(arr, search_element);
    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }
    return 0;
}
</int>

輸出

Element found at index: 4

方法2：根據設計技術對演算法進行分類。

• 分析演算法的設計技巧。

• 將演算法分類為以下類別之一−

  • #Brute-force演算法

  • #分治演算法

  • #貪婪演算法

  • 動態規劃演算法

  • #回溯演算法

#Example-2

的中文翻譯為：

範例-2

下面的程式展示了二分查找演算法的實現，該演算法利用分治策略，具有對數時間複雜度O(log n)。此演算法重複將陣列二分為兩個部分，並檢查中間元素。如果這個中間元素與所尋找的搜尋元素相等，則立即傳回索引。如果中間元素超過了搜尋元素，則在數組的左半部繼續搜索，如果中間元素較小，則在右半部進行搜索。主函數透過初始化數組和搜尋元素，透過排序來排列數組，呼叫binarySearch函數，最後呈現結果。

#include <iostream>
#include <vector>
#include <algorithm>

// Binary search function using divide and conquer technique with logarithmic time complexity O(log n)
int binarySearch(const std::vector<int>& arr, int left, int right, int x) {
   if (right >= left) {
      int mid = left + (right - left) / 2;

      if (arr[mid] == x) {
         return mid;
      }

      if (arr[mid] > x) {
         return binarySearch(arr, left, mid - 1, x);
      }

      return binarySearch(arr, mid + 1, right, x);
   }
   return -1;
}

int main() {
   std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
   int search_element = 5;

   // The binary search algorithm assumes that the array is sorted.
   std::sort(arr.begin(), arr.end());

   int result = binarySearch(arr, 0, static_cast<int>(arr.size()) - 1, search_element);

   if (result != -1) {
      std::cout << "Element found at index: " << result <<std::endl;
   } else {
      std::cout << "Element not found in the array." << std::endl;
   }
   return 0;
}

輸出

Element found at index: 4

結論

因此，在本文中，討論了兩種分類演算法的方法 - 基於它們的時間複雜度和基於它們的設計方法。作為範例，我們介紹了一個線性搜尋演算法和一個二分搜尋演算法，兩者都在C 中執行。線性搜尋演算法採用蠻力方法，具有O(n)的線性時間複雜度，而二分搜尋演算法則利用分治法，呈現O(log n)的對數時間複雜度。對演算法的各種分類的全面理解將有助於選擇特定任務的最佳演算法，並改進程式碼以提高效能。

以上是演算法分類與範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！