Kompleksitas Algoritma

Pada kesempatan kali ini saya ingin sedikit berbagi informasi tentang perbandingan efisiensi dalam sebuah algoritma. Tujuan membandingkan beberapa algoritma ini adalah untuk mengetahui seberapa jauh keefektifan sebuah algoritma dalam meminimumkan kebutuhan waktu dan ruang. Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses. Berikut adalah penjelasan dari 5 algoritma yang digunakan disertai dengan contoh kode program menggunakan python dan grafik pertumbuhan algoritma tersebut dalam memproses data.

1.      O(1) : Kompleksitas Konstan

  Kode Program :

     

   Penjelasan : Implementasi untuk Big-O Notation dengan kompleksitas konstan atau O(1) menggunakan algoritma pertukaran dua buah nilai yang ditulis dalam bahasa python. Algoritma pertukaran dua buah nilai hanya membutuhkan satu buah variabel bantuan yaitu variable temporary. Berikut adalah tahapan perhitungan untuk mendapatkan jumlah langkah yang diperlukan pada algoritma pertukaran dua buah nilai.

Kode	Jumlah Eksekusi
a = 1	1
b = 2	1
temp = a	1
a = b	1
b = temp	1

Disini jumlah operasi penugasan (assignment) ada lima buah dan tiap operasi dilakukan satu kali. Jadi, T(n)  = 5 = O(1).

 Grafik pertumbuhan algoritma dengan kompleksitas konstan :

2.      O(log n) : Kompleksitas Logaritmik

    Kode Program : 

 

   

    Penjelasan : Implementasi untuk Big-O Notation dengan kompleksitas konstan atau O(1)    menggunakan algoritma pencarian biner yang ditulis dalam bahasa python. Algoritma pencarian biner membagi larik di pertengahan menjadi dua bagian yang berukuran sama (n/2 bagian), bagian kiri dan bagian kanan. Jika elemen pertengahahn tidak sama dengan item yang dicari, keputusan dibuat untuk melakukan pencarian pada bagian kiri atau bagian kanan. Proses bagi dua dilakukan lagi pada bagian yang dipilih. Berikut adalah tahapan perhitungan untuk mendapatkan jumlah langkah yang diperlukan pada algoritma pencarian biner :

a.       Inisialisasi first,last,dan found  --> 3 langkah

b.      Pengecekan kondisi while --> 1 langkah

c.       Inisialisasi midpoint --> 1 langkah

d.      Pengecekan if alist[midpoint] == item, kasus terburuk masuk pada else dan menjalankan kode di dalamnya --> 5 langkah.

Sehingga model matematika fungsi Big-O yang didapat adalah 3 + 7 (jumlah perulangan). Karena setiap iterasinya nilai midpoint dibagi 2, maka jumlah data yang akan di proses (n) di potong sebanyak setengahnya maka model matematikanya menjadi f(n) = 7^k f( n/2^k ) di mana kondisi dari pemberhentian perulangan adalah ketika sisa elemen list adalah 1, dengan kata lain :

  n/2^k  = 1 -->  n = 2^k  -->Log₂ n = k

Jadi T(n) = Log₂ n = O (log n)

   Grafik pertumbuhan algoritma dengan kompleksitas logaritmik :

3.      O(n) :  Kompleksitas Linear

        

           Kode Program  :

           

     

     Penjelasan : Implementasi untuk Big-O Notation dengan kompleksitas linier atau O(n) menggunakan algoritma pencarian sequential yang ditulis dalam bahasa python. Algoritma pencarian sequential melakukan pencarian dengan menelusuri elemen-elemen dalam list satu demi satu, mulai dari indeks paling rendah sampai indeks terakhir. Jadi jika data berukuran 10 maka akan memerlukan 10 langkah untuk menyelesaikan pencarian serta jika data berukuran 100 maka akan memerlukan 100 langkah untuk menyelesaikan pencarian. Berikut adalah tahapan perhitungan untuk mendapatkan jumlah langkah yang diperlukan pada algoritma pencarian sequential. 

 

Kode	Jumlah Eksekusi
pos = 0	1
found = false	1
while pos < len(alist) and not found	1
if alist[post] == item	n
found = true	1
else	1
pos = pos +1	1
return found	1

Sehingga kompleksitas dari sequential search adalah 7 + n atau dapat ditulis sebagai O(n).

          Grafik pertumbuhan algoritma dengan kompleksitas linear :

4.      O(n²) :  Kompleksitas Kuadratik

            Kode Program :

   

     Penjelasan : Implementasi untuk Big-O Notation dengan kompleksitas kuadratik atau O(n²) menggunakan algoritma yang menguji apakah dua buah matriks, A dan B, masing-masing berukuran n x n sama yang ditulis dalam bahasa python. Operasi dasar yang dihitung adalah operasi perbandingan elemen-elemen kedua buah matriks sehingga jumlah operasi perbandingan elemen matriks adalah sebanyak T(n)  = n * n = n² kali. Jadi kompleksitas waktu dari algoritma tersebut adalah O(n²).

            Grafik pertumbuhan algoritma dengan kompleksitas kuadratik :

5.      O(n³) : Kompleksitas Kubik

           Kode Program :

     

   Penjelasan : Implementasi untuk Big-O Notation dengan kompleksitas kubik atau O(n³) menggunakan sebuah instruksi assignment dengan tiga buah kalang bersarang yang ditulis dalam bahasa python. Jadi jika n = 100, maka waktu pelaksanaan algoritma adalah 1.000.000 serta jika n dinaikkan menjadi dua kali semula, waktu pelaksanaan algoritma meningkat menjadi delapan kali semula.

Berikut adalah tahapan perhitungan untuk mendapatkan jumlah langkah yang diperlukan pada sebuah instruksi assignment :

a.       Kalang terluar (kalang i) dieksekusi n kali.

b.      Untuk setiap nilai i, kalang terluar kedua (kalang j) dieksekusi n kali.

c.        Untuk setiap nilai j, kalang terdalam (kalang k) dieksekusi j kali, dengan j = 1,2,3,...,n sehingga jumlah pengulangan seluruhnya adalah T(n) = n (1+2+3...+n)=n²(n+1)/2. Jadi T(n) = n²(n+1)/2 . O(1) = O(n³).

       Grafik pertumbuhan algoritma dengan kompleksitas kubik :