Pengelasan dan Contoh Algoritma

Klasifikasi algoritma membantu dalam memilih algoritma yang paling sesuai untuk tugas tertentu, membolehkan pembangun mengoptimumkan kod mereka dan mendapatkan prestasi yang lebih baik. Dalam sains komputer, algoritma ialah set arahan yang jelas digunakan untuk menyelesaikan masalah atau melaksanakan tugas tertentu. Kecekapan dan keberkesanan algoritma ini adalah penting dalam menentukan prestasi keseluruhan program.

Dalam artikel ini, kita akan membincangkan dua cara biasa untuk mengklasifikasikan algoritma, iaitu berdasarkan kerumitan masa dan berdasarkan teknik reka bentuk.

Tatabahasa

Sintaks fungsi utama digunakan dalam kod kedua-dua kaedah -

int main() {
   // Your code here
}

Algoritma

• Kenal pasti masalah yang perlu diselesaikan.

• Pilih kaedah yang sesuai untuk mengklasifikasikan algoritma.

• Tulis kod dalam C++ menggunakan kaedah pilihan anda.

• Kompil dan jalankan kod.

• Analisis output.

Apakah kerumitan masa?

Kerumitan masa ialah ukuran berapa lama algoritma yang diambil untuk dijalankan sebagai fungsi saiz input. Ia adalah satu cara untuk menerangkan kecekapan algoritma dan skalabilitinya apabila saiz input meningkat.

Kerumitan masa biasanya dinyatakan dalam tatatanda O besar, yang memberikan sempadan atas pada masa berjalan algoritma. Sebagai contoh, algoritma dengan kerumitan masa O(1) bermakna masa berjalan kekal malar tanpa mengira saiz input, manakala algoritma dengan kerumitan masa O(n^2) bermakna masa berjalan berkembang secara kuadratik dengan saiz input. Memahami kerumitan masa sesuatu algoritma adalah penting apabila memilih algoritma yang betul untuk menyelesaikan masalah dan apabila membandingkan algoritma yang berbeza.

Kaedah 1: Kelaskan algoritma berdasarkan kerumitan masa

Pendekatan ini merangkumi klasifikasi algoritma berdasarkan kerumitan masanya.

Ini memerlukan tafsiran terlebih dahulu kerumitan tempoh algoritma, dan kemudian mengklasifikasikannya kepada salah satu daripada lima kategori berdasarkan kerumitan masa berlalunya: O(1) kerumitan masa malar, O(log n) sifat kerumitan masa logaritma, O(n) kerumitan masa linear, kerumitan masa kuadratik O(n^2) atau kerumitan masa eksponen O(2^n). Klasifikasi ini mendedahkan keberkesanan algoritma, dan saiz data input dan jangkaan masa siap boleh diambil kira semasa memilih algoritma.

Contoh-1

Contoh-1

Kod di bawah menunjukkan demonstrasi algoritma carian linear, yang mempunyai kerumitan masa linear O(n). Algoritma ini melakukan semakan sistematik elemen dalam tatasusunan untuk menentukan sama ada mana-mana sepadan dengan elemen carian yang ditentukan. Setelah ditemui, fungsi mengembalikan indeks elemen, jika tidak ia mengembalikan -1, menunjukkan bahawa elemen itu tiada dalam tatasusunan. Fungsi utama bermula dengan memulakan tatasusunan dan mencari elemen, memanggil fungsi linearSearch, dan akhirnya memberikan hasil.

<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>

Output

Element found at index: 4

Kaedah 2: Kelaskan algoritma berdasarkan teknik reka bentuk.

• Kemahiran reka bentuk algoritma analisis.

• Kelaskan algoritma ke dalam salah satu daripada kategori berikut −

  • Algoritma brute-force

  • Algoritma Bahagi dan Takluki

  • Algoritma Tamak

  • Algoritma pengaturcaraan dinamik

  • Algoritma penjejakan belakang

Contoh-2

Contoh-2

Atur cara berikut menunjukkan pelaksanaan algoritma carian binari, yang menggunakan strategi bahagi-dan-takluk dan mempunyai kerumitan masa logaritma O(log n). Algoritma berulang kali membahagi tatasusunan kepada dua bahagian dan menyemak elemen tengah. Jika elemen perantaraan ini sama dengan elemen carian yang dicari, indeks dikembalikan serta-merta. Jika elemen tengah melebihi elemen carian, carian diteruskan di separuh kiri tatasusunan, jika elemen tengah lebih kecil, carian diteruskan pada separuh kanan. Fungsi utama memulakan tatasusunan dan mencari elemen, menyusun tatasusunan dengan mengisih, memanggil fungsi Carian binari, dan akhirnya membentangkan hasilnya.

#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;
}

Output

Element found at index: 4

Kesimpulan

Jadi, dalam artikel ini, dua kaedah mengklasifikasikan algoritma dibincangkan - berdasarkan kerumitan masanya dan berdasarkan kaedah reka bentuknya. Sebagai contoh, kami memperkenalkan algoritma carian linear dan algoritma carian binari, kedua-duanya dilaksanakan dalam C++. Algoritma carian linear menggunakan kaedah brute force dan mempunyai kerumitan masa linear O(n), manakala algoritma carian binari menggunakan kaedah divide-and-conquer dan mempamerkan kerumitan masa logaritma O(log n). Pemahaman menyeluruh tentang pelbagai klasifikasi algoritma akan membantu dalam memilih algoritma terbaik untuk tugas tertentu dan menambah baik kod untuk meningkatkan prestasi.

Atas ialah kandungan terperinci Pengelasan dan Contoh Algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!