Big O

Apa itu Big O?

Big O adalah konsep yang digunakan untuk mendeskripsikan efisiensi algoritma.

Ada dua hal penting yang kita harus pikirkan ketika mendesain atau menganalisis suatu algoritma, yaitu kompleksitas ruang dan kompleksitas waktu. Kompleksitas waktu mendeskripsikan kira-kira untuk jumlah data yang tertentu, seberapa cepat algoritma akan berjalan, sementara kompleksitas ruang mendeskripsikan kira-kira berapa data yang harus kita simpan untuk menjalankan algoritma tersebut (ada beberapa algoritma yang tidak membutuhkan kita untuk menyimpan data dalam jumlah yang sama dengan data yang diproses).

Dalam academia, biasanya ada tiga tipe notasi yang digunakan untuk mendeskripsikan runtime, yaitu: Big O, Big Omega dan Big Theta. Big O merupakan deskripsi batas atas runtime dari program yang dianalisa, Big Omega merupakan deskripsi batas bawah runtime dari program yang dianalisa, sedangkan Big Theta merupakan deskripsi paling dekat ke runtime yang sebenarnya. Di industri, Big Theta digunakan seakan-akan ia Big O, dan karena itulah kita akan menggunakan deskripsi tersebut.

Tiga kasus yang dapat digunakan untuk mendeskripsikan runtime atau space complexity sebuah algoritma.

Best Case: Ketika diberikan input tertentu yang membuat proses dapat dilakukan secepat mungkin, atau untuk space sekecil mungkin.

Worst Case: Ketika diberikan input tertentu yang membuat proses hanya dapat dilakukan selambat mungkin, atau kalau untuk space sebanyak mungkin data yang harus disimpan.

Average Case: Ekspektasi runtime rata-rata untuk data yang diinput ke dalam algoritma, atau kalau untuk space rata-rata data yang disimpan.

Tips menentukan Runtime Complexity

• Dropping nilai
  • Ketika menentukan runtime complexity, pastikan semua nilai yang tidak dominan di-drop. Konstan kurang dominan dibandingkan N, maka kalau misalnya ada O(N+1), maka 1 dapat didrop, menghasilkan O(N).
  • Mengapa kita dapat mendropnya begitu saja? Hal ini disebabkan karena notasi Big O untuk runtime menentukan rate of increase dari runtime sebuah algoritma. Konstan 1 tidak akan berubah ketika besar data berubah, sehingga tidak perlu dianggap. Bahkan perkalian dengan konstan pun dapat didrop, misal ada O(5*2^N) maka 5 dapat didrop, yang kemudian akan membuat notasi tersebut menjadi O(2^N).
  • Selain itu, variabel yang non-dominan juga dapat di-drop. Maksud dari variabel yang non-dominan adalah variabel yang tidak memiliki nilai term yang terbesar. Contohnya dalam kasus O(N^2 + N). N^2 memiliki nilai term lebih besar dibandingkan N maka N dapat didrop.
  • Berikut adalah tabel yang diurutkan berdasarkan nilai term, dengan nilai term yang diatas merupakan nilai term yang terkecil.
  • Sedikit info:
    • Jika N dibagi 2 setiap kali iterasi, maka runtimenya untuk porsi kode tersebut Log N
    • Untuk rekursi, eksponensial dengan C merupakan berapa kali pemanggilan fungsi yang akan menyebabkan rekursi. Biasanya keliatan di return. Untuk kasus tipikal, kalo fungsi f(), terus untuk fungsi tersebut kasus yang bakal rekursi return f() + f(), berarti O(2^n), kalo f() + f() + f() berarti O(3^n).
• Multipart algorithm: Tambah atau Kali?
  • Misal ada algoritma yang runtimenya A, dan ada algoritma yang runtimenya B
    • Ketika algoritmanya: Loop A, baru setelah itu Loop B, maka tambahkan jadi O(A + B)
    • Ketika algoritmanya: Setiap kali Loop A, Lakukanlah Loop B, maka kalikan jadi O(A * B)
• Amortized time
  • Khusus untuk ArrayList, yang merupakan dynamic resizing array, ketika arraynya full, dia bakal ngedouble sizenya dengan cara membuat ArrayList baru yang sizenya 2x dari size ArrayList awal dan setelah itu mengkopi semua elemen dari ArrayList yang lama ke ArrayList yang baru. Aksi ini memakan N waktu, tapi jarang terjadi.
  • Kalau arraynya ga penuh kan cuma 1 doang runtimenya. Itulah amortized timenya.
  • Untuk X insertion tapinya, butuh O(2X) time, asumsi array didouble pada power of 2, yaitu 1,2,4,8,16…..X. Hal ini karena X + X/2 + X/4 + X/8……+ 1 mendekati 2. X disini konstan.

Tips menentukan Space Complexity

Satu data merepresentasikan satu konstan. Array yang panjangnya n berarti n data yang harus disimpan. Jika ada array dua dimensi nxn, maka kompleksitasnya n^2. Note bahwa huruf n yang digunakan merupakan huruf kecil, dengan n berarti input size dalam satuan bit yang dibutuhkan untuk merepresentasikan input tersebut.