Algoritma Greedy

    Algoritma greedy merupakan metode yang paling populer untuk memecahkanpersoalan optimasi. Greedy sendiri diambil dari bahasa inggrisyang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.

Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencarinilai maksimum sementara pada setiap langkahnya. Nilaimaksimum sementara ini dikenal dengan istilah local maximum.Pada kebanyakan kasus, algoritma greedy tidak akanmenghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Contoh masalah sehari-hari yang menggunakan prinsipgreedy:

– Memilih beberapa jenis investasi (penanaman modal)

– Mencari jalur tersingkat dari Bandung ke Surabaya

– Memilih jurusan di Perguruan Tinggi

– Bermain kartu remi

   Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi padasetiap langkah solusi. Oleh karena itu, pada setiap langkah harusdibuat keputusan yang terbaik dalam menentukan pilihan.Keputusan yang telah diambil pada suatu langkah tidak dapatdiubah lagi pada langkah selanjutnya.

Kesimpulan

      Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akanmendapatkan solusi yang cukup baik. Meskipun tidak selalumendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistemreal-time atau game.

Dari impementasi yang kita lakukan, dapat dilihat bagaimanaalgoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:

1. Fungsi untuk melakukan penelusuran masalah.

2. Fungsi untuk memilih local maximum dari pilihan-pilihanyang ada tiap langkahnya.

3. Fungsi untuk mengisikan nilai local maximum ke solusikeseluruhan.

4. Fungsi yang menentukan apakah solusi telah didapatkan.

Tentunya fungsi-fungsi di atas juga dapat digabungkan ataudipecah lebih lanjut lagi, menyesuaikan dengan strategi greedy yang dikembangkan.

Resource:

https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html

https://www.it-jurnal.com/pengertian-algoritma-greedy/

Menghitung Kompleksitas Waktu Algoritma Rekursif

1. Algoritma Menghitung Nilai x Pangkat y

Program Pangkat

Kamus

x,y : integer

Function pangkat (x:integer, y: integer)

Algoritma

if y = 0 then

return 1

else

return x*pangkat(x,y-1)

endif

endfuction

algoritma

     input x,y

     output pangkat(x,y)

Analisis:

- Kompleksitas waktu diukur dari jumalh operasi perkalian (*)

- Jika y = 0 maka pangkat sama dengan 1 (tidak ada operasi perkalian) {basis}

     - Jika y > 0 maka,

pangkat(x,y) = x * pangkat(x,y-1) atau x^y =      x * x^y-1  (ada operasi perkalian) {rekurens}

- Yang mempengaruhi jumlah pemanggilan rekursif adalah nilai y atau (y-1) atau T(n-1)

T(n) = 1 + T(n-1) ; n > 0 {rekurens}

T(n) = 1 ; n = 0          {basis}

    

     T(n) = 1 + T(n-1)

           = 1 + 1 + T(n-2)

           = 2 + 1 + T(n-3)

           …

     T(n) = n + T(0)

     Jadi T(n)= n ≈ O(n)

2. Algoritma Menentukan Deret bilangan Fibonacci ke-n

Function fib (input n : integer) → integer

Deklarasi

-

Algoritma

     If (n = 0) or (n = 1) then

           Return n

     Else

           Return fib(n-1) + fib(n-2)

     endif

Analisis:

- Kompleksitas waktu diukur dari jumalh operasi samadengan (=)

n = 0 atau n = 1 {basis}

fib(n-1) + fib(n-2) {rekurens}

- T(n)= 2 + T(n-1) + T(n-1) ; n > 1 {rekurens}

  T(n)= 1 ; n = 0 = 1      {basis}

  T(n-1)≈T(n-2)

  T(n)     = 2T(n-1) + 2

           = 2{2T(n-1)+2}+2

           = 4T(n-2)+6 ; k=2 , C=2

           = 8T(n-3)+14 ; k=3 , C=2

           …

  T(n)     = 2^kT(n-k)+(2^k-1)C

           (n-k) = 0 → k=n

  T(n)     = 2ⁿT(0)+(2ⁿ-1)C

  T(n)     = (1+C)*2ⁿ-C

  Jadi T(n)≈ 2ⁿ ≈ O(2ⁿ)

3. Algoritma

Procedure MinMaks2(input A : TabelInt, i, j : integer, output min, maks : integer) 

{ Mencari nilai maksimum dan minimum di dalam tabel A yang berukuran n elemen secara Divide and Conquer. Masukan: tabel A yang sudah terdefinisi elemenelemennya Keluaran: nilai maksimum dan nilai minimum tabel }

Deklarasi

min1, min2, maks1, maks2 : integer

Algoritma

     if i=j then { 1 elemen }

min ← Ai

maks ← Ai

else

if (i = j-1) then { 2 elemen }

if Ai < Aj then

maks ← Aj

min ← Ai

else

maks ← Ai

min ← Aj

endif

else { lebih dari 2 elemen }

k ← (i+j) div 2  { bagidua tabel pada posisi k } MinMaks2(A, i, k, min1, maks1)

MinMaks2(A, k+1, j, min2, maks2)

if min1 < min2 then

min ← min1

else

min ← min2

endif

if maks1<maks2 then

maks ← maks2

else

maks ← maks2

endif

Analisis:

T(n) = 0; n=1 {basis}

T(n) = 1; n=2 {basis}

T(n) = 2T(n/2)+2 ; n>2 {rekurens}

Asumsi n = 2^k, dengan k bilangn bulat positif, maka:

T(n) = 2T(n/2)+2

     = 2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2

     = 4 (2T(n/8) + 2) + 4 + 2 = 8T(n/8) + 8 + 4 + 2

     = ...           ­_k-1

     = 2k – 1 T(2) +      ∑ 2ⁱ

                     ⁱ⁼¹

     = 2k – 1  1 + 2k – 2

     = 2^(2logn)-1 + 2^(2logn)-2

     = n/2 + n-2

     =3n/2-2

Jadi T(n) = n = O(n)

resource : 

https://bertzzie.com/knowledge/analisis-algoritma/KompleksitasAlgoritma.html

https://www.youtube.com/watch?v=gCsfk2ei2R8

http://documents.tips/documents/analisis-algoritma-non-rekursif-dan-rekursifppt.html#

buku Algoritma dan Pemrograman, Renaldi Munir

Menghitung Efisiensi Waktu Dengan rumus Sigma

1. Algoritma Penjumlahan Deret

Program penjumlahanderet

Deklarasi

n, i, jumlah : integer

Algoritma

Read(n)

jumlah ← 0

For i ←  1 to n do

jumlah ← jumlah + 1

Endfor

Write(jumlah)

Analisis:

_n

∑  = n-1+1

ⁱ⁼¹

    ≈ n ϵ Θ(n)

2. Alagoritma Menampilkan Bintang

Program menampilkanbintang

Deklarasi

i, j, n : integer

Algoritma

Read(n)

For i <- 1 to n do

          For j <- 1 to n do

               Write(‘*’)

          Endfor

     Endfor

Analisis:

_{n     n      n}

∑    ∑ 1 = ∑  n-1+1

^{i=1   j=1    i=1}

             _n

      = ∑  n

         ⁱ⁼¹

      = (n-1)n

           = n²-n ≈ n²  ϵ Θ(n²)

3. Algoritma Mencari Maks

Program mencari_maks (input A : LarikInt, input n : integer, output maks : integer)

Deklarasi

i : integer

Algoritma

maks ß A[1]

for i ß 2 to n do

            if A[i] > maks then

              maks ß A[i]
            endif

endfor

Analisis :

_n

∑  = n-2 +1

ⁱ⁼²

_­   = n-1 _­­^­­ ≈ n ϵ Θ(n)

4. Algoritma Menentukan Faktorial

Program faktorial (input a₁..a_n : integer)

Deklarasi :

i : integer

fak : real

Algoritma :

Input(n)

If (n = 0) or (n = 1) then

faktorial ß 1

Else

                fak ß 1

                for i ß 2 to n do

                           fak ß fak * i

                endfor

     endif

     output(fak)

Analisis:

­_n

∑ = n-2+1

­­­­­­­_­­­­­ⁱ⁼²

   = n – 1 ≈ n ϵ Θ(n)

5. Algoritma Menghitung Rata - rata

Program HitungRataRata

{Menghitung rata - rata N buah bilangan bulat yang dibaca dari papan ketik. N > 0}

Deklarasi

     N, x, i, jumlah : integer

     r : real                  {rata rata nilai}

Algoritma

     Read(N)

Jumlah ß 0

For i ß 1 to N do

     Read(x)

jumlah ß jumlah + x

     endfor

     r ß jumlah/N

     write(r)

Analisis :

_n

∑  = n-1+1

ⁱ⁼¹

   = n ≈ n ϵ Θ(n)