Algoritma dan Kompleksitas
5.2 Minimum dan Maksimum
Berikut ini adalah contoh masalah dalam mencari nilai minimum dan maksimum. Misalkan diberikan tabel A yang berukuran n elemen dan sudah berisi nilai integer, carilah nilai minimum dan maksimum sekaligus di salam tabel tersebut! Penyelesaian dengan Algoritma Brute Force Penyelesaian dengan Algoritma Divide and Conquer Ukuran tabel hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen. Berikut ini contoh algoritmanya. Kompleksitas Waktu Asimptotik Brute Force Vs DANDC MinMaks1 secara brute force : T(n) = 2n – 2 MinMaks2 secara divide and conquer: T(n) = 3n/2 – 2 Perhatikan: 3n/2 – 2 < 2n – 2 , n ? 2. Kesimpulan: Algoritma MinMaks lebih mangkus dengan menggunakan metode Divide and Conquer.