Algoritma Greedy

Pengertian Greedy

Algoritma greedy berasal dari bahasa inggris, yang berarti tamak atau rakus. Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai optimum pada setiap langkahnya. Nilai optimum ini dikenal dengan istilah local optimum. Dengan harapan bahwa langkah sisanya mengarah ke solusi optimum global (Global optimum). Pada banyak kasus algoritma greedy tidak akan menghasilkan solusi paling optimal, akan tetapi algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Oleh karena itu, pada setiap langkah diperlukan keputusan terbaik dalam menentukan pilihan.

Analisa Matematis – Rekursif

Contoh Kasus Analisa Matematis Algoritma Rekursif

Kasus 1 :

Perpangkatan aⁿ ( a bilangan bulat dan n > 0 ) kemudian nyatakan :

aⁿ = a x a x …x a

    = a x a^n-1

Notasi Asimtotik

• Ο ( Big Oh )

Notasi Asimtotik – Kasus 5

Kasus 5

Notasi Asimtotik – Kasus 4

Kasus 4

Diketahui bilangan bulat a₁, a₂, . ., a_n (tidak ada elemen ganda dan sudah terurut menaik). Hitunglah kompleksitas waktu Terbaik( T_min(n)), Terburuk(T_max(n)), dan Rata-rata(T_avg(n)) dari algoritma mencari elemen Maksimum larik dibawah ini.

Notasi Asimtotik – Kasus 3

Kasus 3

Menghitung jumlah pembelian dan diskon.