Kompleksitas Algoritma : Waktu

Hello, pada postingan ini kami akan membahas tentang Kompleksitas Waktu Algoritma, kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang dieksekusi.
Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi tertentu, maka kita dapat menghitung berapa waktu sesungguhnya untuk melaksanakan algoritma tersebut.


                        Dengan rumusan :

Berikut kami memberikan 5 contohnya :

1. Algoritma Jam pasir

       

Pada algoritma di atas terdapat :

• Input = (n + (n - 1) + (n - 1)) . a
• Output = n ^ 2 / n * n (output dari "$" dan (" ") jika disatukan) . b
• Jumlah operasi meliputi :
• <= (kurang dari sama dengan) :  n -1 . c
• >= (lebih besar sama dengan) : n -1 . d
• div : n - 1 . e
• + : n -1 . f
• - : n - 1 . g
• and : n . h
• or : n . i

T(n) = (n + (n - 1) + (n - 1) ) * a + (n * n) * b + (n - 1) * c + (n - 1) * d + (n - 1) * e + (n - 1) * f + (n - 1) * g + n * h + n * i

2.    Algoritma Belah Ketupat

Dari algoritma tersebut terdapat :

• Input = 5 + (5 - 1) + 5 + 4 + 4 + 4 . a
• Output = 5 + (5 - 1) + 5 + 4 + 4 + 4 . b
• - = 4 . c

T(n) = (5 + (5 - 1) + 5 + 4 + 4 + 4)*a + (5 + (5 - 1) + 5 + 4 + 4 + 4)*b + 4*c  

3. Algoritma Index Nilai

Pada algoritma di atas terdapat :

C(n)

• Output = 5  // misalkan a
• Input = 1   // misalkan b
• Jumlah Operasi

1.  ≥ = 4 // misalkan c
2. < = 4  //misalkan d
3.  and = 4 misalkan e

makan nilai T(n)
T(n) = 5a + b + 4c + 4d + 4e

4.Algoritma Pyramid

C(n)
    <- 209  a  (n*n+8n)
    <= 100  b (8n+1)
     +  82    c  (7n+5)
     -   18    d  (n+6)

   T(n) = 209a + 100b + 82c + 18d
   T(n) = (n*n+8n).a + (8n+1).b + (7n+5).c + (n+6).d


5. Menghitung rerata

procedure HitungRerata(input a₁, a₂, ..., a_n : integer, output r : real)

{ Menghitung nilai rata-rata dari sekumpulan elemen larik integer a₁, a₂, ..., a_n.

  Nilai rata-rata akan disimpan di dalam peubah r.

  Masukan: a₁, a₂, ..., a_n

  Keluaran: r (nilai rata-rata)

}

Deklarasi

   k : integer

   jumlah : real

Algoritma

   jumlah¬0

   k¬1

   while k £ n do 

     jumlah¬jumlah + a_k

     k¬k+1

   endwhile

   { k > n }

   r ¬ jumlah/n   { nilai rata-rata }

                  Operasi pengisian nilai (jumlah¬0,  k¬1, jumlah¬jumlah+ak, k¬k+1, dan r ¬ jumlah/n)

          

                  Jumlah seluruh operasi pengisian nilai adalah

                  t1 = 1 + 1 + n + n + 1 = 3 + 2n

                  Operasi penjumlahan (jumlah+ak, dan k+1)

                  Jumlah seluruh operasi penjumlahan adalah

                  t2 =  n + n = 2n 

                  Operasi pembagian (jumlah/n)

                  Jumlah seluruh operasi pembagian adalah

                  t3 = 1

     

                  Total kebutuhan waktu algoritma HitungRerata:

                  t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c  detik

Model perhitungan kebutuhan waktu seperti di atas kurang dapat diterima:

1. Dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu

2. Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya. Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan.

Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler apapun.

Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma.
Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas ruang.

Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n.

Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.

Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan meningkatnya ukuran masukan n. 

Kompleksitas Waktu

Dalam praktek, kompleksitas waktu dihitung berdasarkan jumlah operasi abstrak yang mendasari suatu algoritma, dan memisahkan analisisnya dari implementasi.

Demikian Kumpilan Contoh  Kompleksitas Algoritma Waktu : T(n)
Terima Kasih ...

Sumber : Ebook , Book Note , Modul , Dll