Algoritma Greedy

Definisi Algoritma Greedy

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.

•       Persoalan optimasi (optimization problems): 

              ➔ persoalan mencari solusi optimum.

•       Hanya ada dua macam persoalan optimasi:

                 1.  Maksimasi (maximization)

                 2.  Minimasi (minimization)

Contoh persoalan optimasi:

  ( Persoalan Penukaran Uang): Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

➔ Persoalan minimasi

•       Greedy = rakus, tamak, loba, …

•       Prinsip greedy: “take what you can get now!”.

•       Algoritma greedy membentuk solusi langkah per langkah (step by step).

•       Pada setiap langkah, terdapat banyak pilihan yang perlu dievaluasi.

•       Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

•       Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah;

                   

     Pada setiap langkah:

1          .       Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan.   

2          .       Berharap bahwa dengan memilih langkah optimum local pada setiap langkah akan  berakhir    dengan optimum global.

               

•       Tinjau masalah penukaran uang:

                Strategi greedy: 

                Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa.

•       Misal: A = 32, koin yang tersedia: 1, 5, 10, dan 25

                Langkah 1: pilih 1 buah koin 25  (Total = 25)

                Langkah 2: pilih 1 buah koin 5    (Total = 25 + 5 = 30)

                Langkah 3: pilih 2 buah koin 1    (Total = 25+5+1+1= 32) 

•       Solusi: Jumlah koin minimum = 4     (solusi optimal!)

Elemen-elemen algoritma greedy:

        1. Himpunan kandidat, C.

        2. Himpunan solusi, S

        3. Fungsi seleksi (selection function)

        4. Fungsi kelayakan (feasible)

        5. Fungsi obyektif

Dengan kata lain:

        Algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C;  yang dalam hal ini , S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S  dioptimisasi oleh fungsi obyektif.

Pada masalah penukaran uang:

•       Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.

•       Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.

•       Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.

•       Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.

•       Fungsi obyektif: jumlah koin yang digunakan minimum.

Bantuk umum algoritma greedy

∙          Pada akhir setiap lelaran, solusi yang terbentuk adalah optimum lokal. 

∙          Pada akhir kalang while-do diperoleh optimum global.

Contoh Soal

Contoh 1: tersedia banyak koin 1, 5, 10, 25

•       Uang senilai A = 32 dapat ditukar dengan banyak cara berikut:

                  32 = 1 + 1 + … + 1                            (32 koin)

                  32 = 5 + 5 + 5 + 5 + 10 + 1 + 1      (7 koin)

                  32 = 10 + 10 + 10 + 1 + 1                               (5 koin)

                  … dst                  

•       Minimum: 32 = 25 + 5 + 1 + 1       (4 koin)

Contoh 2: tinjau masalah penukaran uang.

        (a)          Koin: 5, 4, 3, dan 1

                        Uang yang ditukar = 7.

                        Solusi greedy:  7 = 5 + 1 + 1           ( 3 koin) → tidak optimal

                        Solusi optimal: 7 = 4  + 3                                ( 2 koin)

        (b)          Koin: 10, 7, 1

                        Uang yang ditukar: 15

                        Solusi greedy:  15 = 10 + 1 + 1 + 1 + 1 + 1 (6 koin)

                        Solusi optimal: 15 = 7 + 7 + 1                                        (hanya 3 koin)

        (c)           Koin: 15, 10, dan 1

                        Uang yang ditukar: 20

                        Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1  (6 koin)

                        Solusi optimal: 20 = 10 + 10                                          (2 koin)

Contoh Kasus Algoritma Greedy

1. Masalah penukaran uang

        Nilai uang yang ditukar: A

        Himpunan koin (multiset):  {d₁, d₂, …}.

        Himpunan solusi: X = {x₁, x₂, …, x_n},

                        x_i = 1 jika d_i dipilih, x_i = 0 jika d_i tidak dipilih.

Penyelesaian dengan algoritma greedy

•       Strategi greedy:  Pada setiap langkah, pilih koin dengan nilai  terbesar dari himpunan koin yang tersisa.

•       Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan yang menurun (noninceasing order).

•       Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n).

•       Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu menghasilkan solusi optimal (lihat contoh sebelumnya).  

2. Minimisasi Waktu di dalam Sistem (Penjadwalan)

•       Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan i adalah t_i.

                Minimumkan total waktu di dalam sistem: 

                T =          (waktu di dalam sistem)

•       Ekivalen dengan meminimumkan waktu rata-rata pelanggan di dalam sistem. 

Penyelesaian dengan algoritma greedy

                 Strategi greedy: Pada setiap langkah, pilih pelanggan yang membutuhkan waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.

Categorized Tugs Tutorial Blog

Algoritma Rekursif

• Function pangkat(a : integer; n : integer):integer;
  
       if n = 0 then
       begin
           pangkat := (1);
       end
       else
       begin
           pangkat := (a*pangkat(a, n-1));
       end;
  
  endfuction
• Algoritma Menentukan Deret Bilangan Fibonacci
  
  Deklarasi:
  
  i, n, fibonacci(i): integer
  
  Deskripsi:
  
  input(n)
  if i=0 atau i=1 then
  cetak “fibonacci(i)=i”
  else
  while i>1 dan i=n do
  fibonacci(i)=fibonacci(i-1)+fibonacci(i-2)
  cetak fibonacci(i)
  i=i+1
  end
• Function gcd(m, n : integer) : integer;
  var r : integer;
  begin
      r := m mod n;
  
      while (r <> 0) do begin
          m := n;
          n := r;
          r := m mod n;
      end;
  
      gcd := n;
  end;
        Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);

Tugas 1

Program perulangan;

Deklarasi :

  i : integer;

Algoritma :

  i ← 2

    while i < 5 do

        output  (i, ' KALI PERULANGAN')

          i ← i + 1;

    endwhile

end.

Analisis :

T(n) = cop.c(n)

←           : 4n

<             : 4n

+             : 3n

ouput      : 3n

T(n) = (4n)a + (4n)b + (3n)c + (3n)d

T(2) = 8a + 8b + 6c + 6d

Program ganjil_genap;

Deklarasi :

  a : integer;

Algoritma :

  output  (' MASUKKAN BILANGAN : ')

    if (a mod 2 = 0) then

      output ('genap')

    else

      output ('ganjil')

    endif

end.

Analisis :

T(n) = cop.c(n)

mod        : 1

=             : 1

T(n) = 1a + 1b

T(1) = 1a + 1b

Program perkalian;

Deklarasi :

n           : integer;

x           : integer;

angka   : integer;

hasil     : integer;

Algoritma :

  n ← 1;

  angka ← 10

  while n  <=  9 do

     x ← n + 1;

     hasil ← x * angka;

     output (x, ' * ', angka, ' = ', hasil);

     n ← n + 1;

  endwhile

end.

Analisis :

T(n) = cop.c(n)

←           : 3n + 1

<=           : n + 9

+             : 2n

*             : 1

T(n) = (3n + 1)a + (n + 9)b + (2n)c + 1d

T(1) = 4a + 10b + 2c + 1d

Program volume_balok;

Deklarasi :
  panjang               : real;

lebar                    : real;

tinggi                   : real;
  volume                : real;

Algoritma :
  output ('Program Volume Balok')
  output ('Masukkan Data')
  output ('Panjang cm =  ')
  input (panjang)
  output ('Lebar   cm =  ')
  input (lebar)
  output ('Tinggi  cm =  ')
  input (tinggi)

  volume ← panjang * lebar * tinggi;
  output ('Hasil Volume =  ',  volume : 4 : 2,  ' cm ^ 3 ');
end.

Analisis :

T(n) = cop.c(n)

*             : 2

T(n) = 2a

Procedure sequential_search (input : LarikInt, input n : Integer, input x : integer, output ketemu : boolean)

Deklarasi :

  i             : integer;

Algoritma :

  i ← i + 1

  while (i < n) and (L[i] <> x) do

    i ← i + 1

  endwhile

  if L[i] = x then

    ketemu ← true

  else

    ketemu ← false

endProcedure.

Analisis :

T(n) = cop.c(n)

←           : 2 + (n - 1)

+             : 1 + (n - 1)

<             : n

<>           : n

=             : 1

T(n) = (2 + (n - 1))a + (1 + (n - 1))b + nc + nd + e

T(1) = 2a + b + c + d + e

 

Categorized Tugs

Kompleksitas Waktu Dan Ruang

Program parkir;

Deklarasi :

  jenis                    : string;

  harga_jenis         : integer;

  lama_parkir         : integer;

  total                     : integer;

Algoritma :

  input (jenis)

  input (lama_parkir)

  if (jenis = “Motor”)

    then

      harga_jenis ← 1500

    else

      harga_jenis ← 2500

  endif

  if (lama_parkir <= 5)

    then

      total ← harga_jenis * lama_parkir

    else

      total ← harga_jenis * 5

  endif

  output (total)

end.

Analisis :

Operator = ←

Tmin(n) = 2n

•    Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 2n

• Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• · Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = n² 

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

n² € O (n²)

n² ≤ 2n² ( untuk semua n ≥ 0 )

n² ≤ 2n²

n² ≤ 2n²

C= 2 , Nₒ=0

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

n² € Ω(n⁻¹)

n² ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

n²€ Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

n²≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

n² ≥ n⁻¹

C₂=1,Nₒ=0

Program indeks_massa_tubuh;

Deklarasi :

  berat_badan    : integer;

  tinggi_badan    : integer;

  tinggi_massa   : real;

  imt                   : real;

 Algoritma :

  input (berat_badan)

  input (tinggi_badan)

  tinggi_massa ← tinggi_badan / 100

  imt ← berat_badan / (tinggi_massa * tinggi_massa)

  if (imt <= 14.9)

    then

      output (“SANGAT KURUS”)

    else

      if ((imt >= 15.0) and (imt <= 18.4))

        then

          output (“KURUS”)

        else

          if ((imt >= 18.5) and (imt <= 22.9))

            then

              output (“NORMAL”)

            else

              if ((imt >= 23.0) and (imt <= 27.4))

                then

                  output (“MASSA TUBUH BERLEBIH”)

                else

                  if ((imt >= 27.5) and (imt <= 40.0))

                    then

                      output (“OBESITAS”)

                    else

                      if ((imt > 40.5)

                        then

                          output (“SANGAT OBESITAS”)

                      endif

                    endif

                  endif

               endif

             endif

          endif

end.

Analisis :

Operator = Output

Tmin(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

 

Tmax(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = (1/2n(1+1))/n = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Program menghitung_diskon;

Deklarasi :

  nilai_belanja           : integer;

  input_diskon           : real;

  diskon                      : real;

  harga_belanja        : real;

const

  ketentuan_diskon = 100000;

  skala_persentase = 100;

Algoritma :

  output ('Masukan jumlah nilai belanja anda = ')

  input (nilai_belanja)

    if (nilai_belanja >= ketentuan_diskon) then

      output ('Masukan jumlah diskon dalam skala persentase 1 s/d 100 = ')

      input (input_diskon)

      diskon ←  nilai_belanja * input_diskon / skala_persentase

      harga_belanja ← nilai_belanja - diskon

      output ('Pembeli mendapat diskon sebesar Rp. ', round(diskon))

      output ('Total nilai belanja yang harus dibayar adalah Rp. ', round(harga_belanja))

      if (nilai_belanja < ketentuan_diskon) then

        output ('Pembeli tidak mendapat diskon')

        output ('Total nilai belanja yang harus dibayar adalah Rp. ', nilai_belanja)

      endif

    endif

end.

Analisis :

Operator = ←

Tmin(n) = 2n

•    Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 2n

• Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• · Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = n² 

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

n² € O (n²)

n² ≤ 2n² ( untuk semua n ≥ 0 )

n² ≤ 2n²

n² ≤ 2n²

C= 2 , Nₒ=0

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

n² € Ω(n⁻¹)

n² ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

n²€ Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

n²≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

n² ≥ n⁻¹

C₂=1,Nₒ=0

Procedure mencetak_angka;

Deklarasi :

  angka           : integer;

Algoritma :

  Input (angka)

    if angka = 1 then

      output (“satu”)

    else

      if angka = 2 then

        output (“dua”)

      else

        if angka = 3 then

          output (“tiga”)

        else

          if angka = 4 then

            output (“empat”)

         else

           output (“angka yang dimasukkan salah”)

         endif

       endif

     endif

   endif

endprocedure.

Analisis :

Operator = (=)

Tmin(n) = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 4n

•          Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

4n € O (n²)

4n ≤ 4n+n ( untuk semua n ≥ 1)

4n ≤ 5n

4n ≤ 5n²

C= 5 , Nₒ=1

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

4n € Ω (n⁰)

4n ≥ n⁰ (untuk semua n ≥ 1)

C=1 , Nₒ=1

•       Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

4n ≤ n²

C₁=4 ,Nₒ=1

-Batas Akhir

T(n) ≥ (n⁰)

4n ≥ n⁰

C₂=1,Nₒ=1

Tave(n) = (n+4n) / 2 = 5n ₊ 

•          Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

5n+2⁻¹ € O (n²)

5n+2⁻¹ ≤ 5n+n ( untuk semua n ≥ 2 )

5n+2⁻¹  ≤ 6n

6n ≤ 6n²

C= 6 , Nₒ=2

•        Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

5n+2⁻¹  € Ω(n⁻¹)

5n+2⁻¹ ≥ 5n - n (untuk semua n ≥ 1)

5n+2⁻¹ ≥ 4n

4n ≥ 4n⁻¹

C=4 , Nₒ=1

•         Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

5n+2⁻¹  € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

5n+2⁻¹ ≤ 5n +n

5n+2⁻¹ ≤ 6n

6n ≤ 6n²

C₁=6 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

5n+2⁻¹ ≥ 5n – n

5n+2⁻¹ ≥ 4n

 4n ≥ 4n⁻¹

C₂=4,Nₒ=1

Procedure {Menjumlahkan atau mengalikan sebuah bilangan dengan 10, bergantung pada nilai x}

Deklarasi

m : integer

x : integer

Deskripsi

m ← 1

read (x)

while x ≠ 0 do

if x mod 2 then

m ← m+10

else

m ← m*10

endif

read(x)

endwhile

write(m)

Analisis : 

Operator - ←

Tmin(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) :  (1/2n(1+n))/2

 

Categorized Tugs