Desain algoritma mengacu pada proses menciptakan solusi untuk suatu masalah dalam bentuk langkah-langkah terstruktur. Tujuannya adalah membuat algoritma yang:
Benar: Menyelesaikan masalah sesuai spesifikasi.
Efisien: Menggunakan sumber daya (waktu dan ruang) secara optimal.
Mudah dipahami: Memiliki struktur yang jelas dan terorganisir.
Teknik Desain Algoritma
Beberapa teknik umum dalam desain algoritma meliputi:
Divide and Conquer
Membagi masalah menjadi submasalah yang lebih kecil, menyelesaikan masing-masing, lalu menggabungkan hasilnya.
Contoh: Merge Sort, Quick Sort.
Dynamic Programming
Memecah masalah menjadi submasalah yang tumpang tindih, menyimpan hasilnya (memoisasi), dan menghindari penghitungan ulang.
Contoh: Fibonacci, Knapsack Problem.
Greedy Algorithm
Mengambil langkah terbaik di setiap tahap dengan harapan solusi global juga optimal.
Contoh: Huffman Coding, Kruskal's Algorithm.
Backtracking
Mencoba semua kemungkinan solusi secara sistematis, dan mundur jika menemui jalan buntu.
Contoh: Sudoku Solver, N-Queens Problem.
Brute Force
Mencoba semua kombinasi untuk menemukan solusi.
Contoh: Traveling Salesman Problem (untuk kasus kecil).
Analisis algoritma bertujuan untuk memahami dan membandingkan kinerja algoritma berdasarkan:
Efisiensi Waktu (Time Complexity): Mengukur jumlah operasi sebagai fungsi dari ukuran input.
Efisiensi Ruang (Space Complexity): Mengukur jumlah memori yang digunakan selama eksekusi.
Kompleksitas Algoritma
Notasi Asimptotik
Big-O (O): Batas atas waktu eksekusi dalam skenario terburuk.
Omega (Ω): Batas bawah waktu eksekusi.
Theta (Θ): Menyatakan batas atas dan bawah dalam skenario rata-rata.
Kelas Kompleksitas
Constant (O(1)): Waktu eksekusi tetap, tidak tergantung pada ukuran input.
Logarithmic (O(log n)): Waktu eksekusi tumbuh secara logaritmik (misalnya, Binary Search).
Linear (O(n)): Waktu eksekusi sebanding dengan ukuran input (misalnya, Linear Search).
Quadratic (O(n²)): Waktu eksekusi tumbuh dengan kuadrat ukuran input (misalnya, Bubble Sort).
Exponential (O(2ⁿ)): Waktu eksekusi tumbuh secara eksponensial (misalnya, penyelesaian masalah dengan brute force).
Identifikasi Masalah
Pahami spesifikasi masalah dan persyaratan yang diberikan.
Pilih Teknik Desain
Pilih pendekatan desain berdasarkan jenis masalah.
Implementasi Algoritma
Tuliskan algoritma dalam bentuk pseudocode atau kode nyata.
Analisis Algoritma
Hitung kompleksitas waktu dan ruang algoritma.
Evaluasi dan Optimasi
Bandingkan dengan algoritma lain dan optimalkan jika diperlukan.