Pada saat mengikuti conference ICITEE di Jogja minggu lalu, ada satu hal yang “menghantui” sampai sekarang. Kronologinya begini:

Di suatu sesi, dengan presenter yang berasal dari salah satu perguruan tinggi di Indonesia, ada satu bagian ketika beliau memaparkan tentang algoritma yang dipakai. Tiba saat kita maju bersamaaa sesi tanya jawab, seorang peserta (kalau tidak salah dari Thailand) menanyakan tentang computational complexity dari algoritma yang dipaparkan. Sang presenter menjawab dengan enteng “it is not really complex, in my computer it only takes about … milliseconds, dan kemudian membahas hal yg justru diluar scoop pertanyaan” (saya kutip persis seperti yang diomongkan, tetapi saya lupa berapa ms tepatnya :D). Sang penanya nampak belum puas, tetapi keburu dihentikan oleh alokasi waktu.

Saya termasuk orang yang berposisi sama dengan sang penanya, belum “ngeh” dengan jawaban yang diberikan, and become awkward to him. Setelah sesi, sebenarnya ingin bertemu dengan sang presenter untuk meluruskan masalah, tetapi keburu menghilang 😀

Meluruskan masalah ?? Dimana letak permasalahannya ??

Tidak ada yang salah dengan tipe jawaban di atas. Hanya saja dalam computer engineering, ketika panjenengan ditanya tentang computational complexity dari algoritma yang dibuat, satuan milliseconds bukanlah jawaban yang umum dan resmi diinginkan, apalagi sekedar bilang algoritma ini cepat dan ndak terlalu kompleks. Sekarang panjenengan bayangkan, misalkan sampeyan membuat algoritma yang berjalan 5 seconds di komputer sampeyan yang spek nya intel i5. Kalau dijalankan di Pentium 3 tentu waktu komputasinya akan berubah jauh.

Computational complexity (lebih tepatnya dalam konteks ini adalah time complexity of algorithms), dalam buku-buku teks sering dinotasikan dengan Big-O, misalnya O(n), O(log n), O(n^2), dst. Ini merupakan ukuran waktu yang diperlukan oleh sebuah algoritma untuk memproses input data yang diberikan (runtime yang dibutuhkan untuk menyelesaikan n data yang diberikan). Ada pula yang mendefinisikan sebagai ukuran berapa kali/lama setiap data n akan dievaluasi dalam sebuah algoritma. Biasanya, complexity berkaitan dengan loop dan conditional block yang digunakan dalam algoritma (tidak selalu demikian). Secara sederhana, jika panjenengan punya data sebanyak n, kemudian sampeyan punya algoritma yang memproses data sebesar n itu, dan perbandingan waktu yang dibutuhkan untuk memproses 10 data dan 1.000.000 data adalah 100.000 kali lipat, maka dalam hal ini dikatakan algoritma sampeyan ini memiliki complexity yang linear, atau dinotasikan dengan O(n).

Lalu, apakah ada algoritma yang complexity-nya quadratic atau yang lainnya ? Ada banyak. Kita ambil contoh algoritma berikut (dari dreamcode)

Array Assignment

for i = 0, i < numData, i = i + 1
     A[i] = 0
end for

Kita anggap, n=numData. Secara sekilas saja, kita bisa menebak bahwa proses yang dilakukan adalah linear sebanyak jumlah data n. Kalau ingin dijabarkan lebih lanjut, proses di atas dapat dipecah menjadi operasi berikut:

• operasi assignment i=0, sebanyak 1 operasi
• operasi comparison i<numData, sebanyak n kali
• operasi aritmatika i=i+1, sebanyak n kali
• operasi assignment array A[i]=0, sebanyak n kali

Total = 3n+1 (jika operasi assignment di tiap-tiap bagian tidak diabaikan, menjadi 6n+1). Dalam computational complexity, kita biasanya tidak menghiraukan constant dan coefficient, sehingga Total = n. Artinya, algoritma di atas memiliki compexity O(n).

Binary Search

function binary_search(A[numData], key, imin, imax)
  while (imax >= imin)
     imid = midpoint(imin, imax)
     if(A[imid] == key)
        return imid
     else if (A[imid] < key)
        imin = imid + 1
     else
        imax = imid - 1
  return KEY_NOT_FOUND

Dengan cara yang sama, kita akan mendapatkan Total ~ log n, sehingga complexity dari binary search menjadi O(log n).

Penjelasan di atas merupakan penyederhanaan yang terlalu sederhana :D. Bagi yang ingin lebih mendalami, silahkan dirujuk pada kuliah online

Coursera

Atau langsung saja search dengan kata kunci computational complexity.

Wiki

Contoh complexity dari beberapa algoritma terkenal

Big-O-cheatsheet

 

source image : https://en.wikipedia.org/wiki/Computational_complexity_theory