Menghitung Kompleksitas Algoritma

Saat ini dimana komputer sudah canggih terkadang pengguna tidak terlalu memperhatikan seberapa kompleks sebuah algoritma. Tinggal jalankan, jika proses terasa lama dan berat, maka algoritma yang diterapkan dalam sebuah bahasa pemrograman berarti “boros” perhitungan. Sedikit memanipulasi dan kemudian dijalankan ulang maka diketahui apakah modifikasi menghasilkan eksekusi yang lebih baik atau tidak. Hal ini tidak dapat dijumpai ketika jaman dahulu dimana komputer belum secanggih saat ini yang bahkan sebuah kalkulator pun belum diciptakan. Dalam mata kuliah algoritma selalu dibahas bagaimana menghitung biaya sebuah algoritma yang diistilahkan dengan time complexity, atau terkadang disebuh kompleksitas saja.

Kalang (Loop) dan Rekursif (Recursive)

Ada dua jenis proses terkenal yang ditemukan oleh pakar-pakar algoritma. Yang pertama adalah kalang dalam sebuah iterasi. Jenis proses ini merupakan jenis yang paling banyak diketahui atau dinalar oleh mahasiswa yang belajar algoritma karena alurnya yang mudah dicerna. Tinggal mensimulasikan tiap iterasi, diketahui hasilnya. Biasanya untuk kasus yang rumit dalam skripsi/tugas akhir, mahasiswa hanya diminta menjalankan satu atau dua iterasi saja sekedar membuktikan bahwa yang bersangkutan memahami proses kerja algoritmanya dan selanjutnya tinggal eksekusi pada komputer yang meneruskan.

Sebagai ilustrasi, misalnya kita memiliki sekumpulan data sebanyak tiga buah, a={1,3,5}. Di sini n menyatakan jumlah data, yaitu tiga buah. Algoritma sederhana penjumlahan seluruh data dengan kalang ditunjukan oleh gambar berikut:

Kolom paling kiri menunjukan algoritma penjumlahan (Sum) data “a” sebanyak “n”. Jadi jika dijalankan akan terjadi perhitungan 0+(1+3+5)=8. Angka 1 di kolom berikutnya merepresentasikan “sekali eksekusi”. Di sini tidak dalam bentuk berapa detik atau milidetik karena tergantung prosesor yang dimiliki sehingga hanya dinyatakan dengan satuan eksekusi/step. Dimulai dari inisialisasi “s” yang dihitung satu step, kalang “for” sebanyak n+1 dengan “+1” perlu ditambahkan mengingat n=0 pun tetap dihitung satu step. Operasi di dalam kalang (akumulasi s) dihitung sebanyak “n” data. Akhir sebuah fungsi, yaitu “return” dihitung sekali. Jadi total 2n+3 langkah. Untuk contoh kasus kita adalah 2(3)+3 atau sebesar 9 langkah. Nah, untuk yang rekursif agak ribet sedikit.

Rekursif adalah fungsi yang memanggil diri sendiri. Untuk contoh penjumlahan data, rekursif di kolom kiri menyatakan fungsi RSum yang menambahkan sebuah data ke-n dengan data sebelumnya (n-1) dan berhenti ketika n nol atau negatif. Untuk data a={1,3,5} di atas operasi yang dilakukan algoritma rekursif adalah (((0)+1)+3 )+5)=8. Di sini perlu variabel x yang berisi kompleksitas (n-1). Tanpak jika n=0 (tidak ada data) jika dieksekusi tetap dibutuhkan 2 step (if dan return). Untuk contoh kita maka kompleksitasnya berarti 2+(2+(2+(2))) atau sebesar 8 langkah dimana kurung menyatakan proses rekursifnya. Atau secara sederhana berarti (n+1)*2. Pastikan dengan n lain yang lebih besar, misalnya 100 untuk memastikan mana yang lebih sedikit langkahnya. Untuk kalang: 2(100)+3=203 dan rekursif: (100+1)*2=202. Contoh lain yang lebih rumit misalnya untuk penjumlahan matriks berikut ini:

Untuk matriks a dan b berukuran misal m=2 baris dan n=3 kolom memiliki kompleksitas 2(2)(3)+2(2)+1 atau sebesar 17 langkah.

Ringkasan

Singkatnya, untuk kondisi if, total step adalah 1 baik ada atau tidak ada data. Return stepnya 1 jika tidak kosong. Kalang for (atau while) membutuhkan n+1 step dengan +1 perlu ditambahkan karena data kosong pun tetap dihitung 1 step. Contoh di atas diambil dari buku karya Ellis Horowitz (Computer Algorithms). Sekian, semoga bermanfaat.

Tentang rahmadya

I'm a simple man .. Lahir di Sleman Yogyakarta, 7 Juni 1976 PENDIDIKAN: TK : - (tidak ada TK di tj Priok waktu itu) SDN : Papanggo, Jakarta 83 - 89 SMPN : 129, Jakarta 89 - 92 SMAN : 8, Yogyakarta 92 - 95 Univ. : Fak. Teknik UGM, Yogyakarta 95 - 2001 Pasca. : Tek. Informatika STMIK Nusa Mandiri, Jakarta 2008 - 2010 Doctoral : Information Management Asian Institute of Technology, Thailand 2013 - 2018 PEKERJAAN: Tek. Komputer AMIK BSI Jakarta : 2002 - 2005 IT Danamon Jakarta : 2005 - 2008 Tek. Informatika STMIK Nusa Mandiri Jakarta : 2005 - 2008 Univ. Darma Persada Jakarta: 2008 - 2013 Fakultas Teknik Universitas Islam "45" Bekasi : 2008 - Skrg ( Homebase) Univ. Bhayangkara Jakarta Raya: 2018 - Skrg Univ. Nusa Putra Sukabumi: 2018 - Skrg
Pos ini dipublikasikan di Algoritma. Tandai permalink.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google

You are commenting using your Google account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.