Ali Jaya Meilio

Level	Beginner
Type	General
Requirement
Similar

Ok sekarang kita bahas sesuatu yang seharusnya setidaknya dimengerti oleh programmer manapun :-?... (well gak harus, tapi ini lumayan penting menurut aku).

Yaitu Big O Notation, contohnya kayak gini :

• O(1)
• O(N)
• O(N^2)
• O(N^3)
• O(sqrt(N))
• O(log N)
• O(N log N)
• O(N!)
• O(2^N)

Dan pertanyaannya adalah itu apaan?

Jadi suatu algoritma biasanya kompleksitasnya dinilai dengan Big O Notation, kompleksitas itu bisa dibedain jadi time complexity (berapa lama algo itu jalan), dan space complexity (berapa banyak memori yang bakal dipake oleh algo itu).

Aku bakal jelasin di time complexity aja seh, karena kalau udah ngerti itu maksudnya apaan, bisa langsung dianalogiin untuk space complexity.

Jadi dalam suatu algo itu biasanya kita dikasih satu set data, kita bisa bilang banyaknya data itu adalah N.

Jadi kalau algo kita O(1) artinya seberapa besar data yang dikasih waktu yang diperlukan algo kita itu gak bergantung besarnya data, misalnya data sebanyak 10 biji diselesaikan dalam 1 detik, nah data yang 1000 biji juga selese dalam 1 detik.

Kalau O(N) artinya waktu yang diperlukan itu sebanding (berbanding lurus) dengan banyaknya data, artinya misal data sebanyak 10 biji diselesaikan dalam 1 detik, maka data 1000 biji diselesaikan dalam 100 detik. (data menjadi gede 100 kali, waktu diperlukan menjadi gede 100 kali juga).

Dan kalau O(N^2) artinya waktu yang diperlukan itu berbanding kuadrat dengan banyaknya data, artinya misal data sebanyak 10 biji itu selese dalam 1 detik, maka data 1000 biji itu selese dalam 10000 detik. (data gede 100 kali, waktu jadi 100*100 = 10000 kali!).


Jadi biasanya waktu itu dihitung dari berapa banyak jumlah operasi yang dilakukan algoritma itu. Untuk operasi sederhana, seperti penjumlahan, perkalian, dsb itu dianggap satu operasi.

Misalnya ada algoritma ini

a = b + c;

Artinya ini algo kompleksitasnya O(1);

Dan kalau ini

a = b + c;
d = e + f;

Ini kompleksitasnya O(2)? Bukan ini masih tetep O(1). Tapi... tapi kan... yang algo yang kedua pasti dua kali lebih lambat dari algo pertama, yups jawabannya iya. Tapi kan kompleksitas itu dihitung berbanding dengan jumlah data, bukan lamanya :-?... *well aku kayaknya jelek menjelaskannya*.

Ok lanjut dulu deh... kalau loop sederhana seperti ini

for(int i=0; i<N; i++)
{
  a++;
}

Untuk data sebesar N, dia melakukan operasi sebanyak N kali, sehingga kompleksitasnya O(N).

Dan untuk kasus ini

for(int i=0; i<N; i++)
{
  a++;
  b++;
}

Well banyak operasi di dalam loop yang dilakukan seh 2*N kali (gak termasuk menambahkan i dan ngecek2 i<N), tapi kompleksitasnya tetep O(N).

Jadi bisa dibilang dalam Big O Notation konstanta seperti 2 pada O(2N) itu bisa dihilangkan menjadi O(N), karena itu sama aja.

Dalam Big O Notation kita lebih memperhatikan bagaimana besarnya data itu mempengaruhi kompleksitasnya dibandingkan seberapa banyak operasi yang sebenarnya dijalankan.


Trus, untuk O(N^2), bisa dikira2 gini contohnya

for(int j=0; j<N; j++)
{
  for(int i=0; i<N; i++)
  {
    a = max(a, i*j);
  }
}

Untuk data sebesar N, banyaknya operasi yang dijalankan yaitu N*N, karena for yang terluar ngeloop sebanyak N kali loop dalam yang ngeloop N kali.
Dan hal ini sama dengan O(N^3).

Dan coba tebak kompleksitas untuk kode berikut

for(int j=0; j<M; j++)
{
  for(int i=0; i<N; i++)
  {
    a = max(a, i*j);
  }
}

Ok, pasti bisa nebak kan kalau ini kompleksitasnya O(NM).


Ok sekarang yang lumayan agak rumit.

for(int j=0; j<N; j++)
{
  for(int i=0; i<=j; i++)
  {
    a = max(a, i*j);
  }
}

Well kompleksitasnya apaan ya? Kalau dilihat jumlah operasinya, misalkan N = 10, maka jumlah operasinya ada sebanyak 1+2+3+...+10 = 55. Artinya jumlah operasinya itu N*(N+1)/2 kan? Tapi ini bisa dijaddiin (N^2 + N)/2, artinya kompleksitasnya O(1/2 * (N^2 + N)), tapi kan konstanta harus dihilangin, jadi O(N^2 + N).
Nah sampe sini, terserah seh mau gimana, tapi biasanya orang2 memilih untuk menghilangkan N karena N^2 jauh lebih signifikan ngaruhnya dari N, jadi bisa dibilang kompleksitas algo di atas itu O(N^2).
Again N^2 itu bukan berapa banyak operasi yang dilakuin, tetapi proporsi kompleksitas terhadap banyaknya data.

Cara lain untuk menentukannya adalah biasanya orang cari worstcase dari loopnya, jadi untuk loop terluar udah pasti ngeloop sebanyak N, dan loop yang didalam itu berdasarkan j, nah kita cari worstcase yang bisa j hasilkan yaitu N, jadi O(N*N) = O(N^2).

Well, ada juga yang lebih aneh dan susah dihitung kompleksitasnya, menghitung kompleksitas tidak hanya sebatas for dan kali - kali doang, ada yang lebih kompleks.
Misalnya ini

var x = N;
while(x > 1)
{
  x = x /2;
}

Well berapa kompleksitasnya?
Kalau kita ngitung dari banyak operasi yang dilakukan, misalkan N = 10, maka tiap loop akan mengubah x menjadi 5, 2, 1, artinya ada sebanyak 3 operasi. Kalau N = 20, maka nanti akan menjadi 10, 5, 2, 1, ada sebanyak 4 operasi. N = 30, maka akan menjadi 15, 7, 3, 1, masih 4. Kalau N = 100, maka akan menjadi 50, 25, 12, 6, 3, 1, ada 6 operasi. Padahal N berubah dari 10 menjadi 100 (10 kali), tetapi jumlah operasinya hanya menjadi 2 kali lebih banyak doang. Tentu ini bukan linear O(N), jadi apa? Ok contoh lagi, N = 1000, maka akan menjadi 500, 250, 125, 62, 31, 15, 7, 3, 1, banyak operasi 9, padahal dari 10 menjadi 1000 itu 100 kali, tetapi banyak operasinya hanya dari 3 menjadi 9, cuman 3 kali doang.

Jadi caranya untuk mengira2 adalah kira2 artinya kita membagi N dengan 2 pangkat D, dimana D adalah banyaknya operasi supaya N/(2^D) = 1.
Artinya Nx = 2^D
Yang artinya juga D = 2log(N)
Jadi banyaknya operasi itu 2log(N), jadi kompleksitasnya O(2log(N)), tapi karena 2log(N) itu sama dengan log(N)/log(2), dan log(2) itu konstan, maka bisa dibuang dan untuk simpelnya cuman ditulis O(log N).

Jadi intinya nyari kompleksitas kadang2 bisa gampang banget, kadang2 bisa belibet banget, dan kadang2 kita buat algo dan kita gak tau kompleksitas algo kita karena terlalu belibet LOL.
Sebenernya kompleksitas dalam Big O Notation ini lebih make sense kalau di plotting ke graph, dengan sumbu x adalah banyak data, dan sumbu y untuk banyaknya operasi yang dijalankan.
Dan kompleksitas adalah bentuk dari grafiknya.
Untuk O(1), grafik akan lurus secara horizontal.
Untuk O(N), grafik akan miring lurus ke kanan atas.
Untuk O(N^2), grafik akan membentuk grafik kuadrat, dimana ada lengkungan di sebelah kanan bawah
Untuk O(N^3), grafik mirip dengan O(N^2) dengan lengkungan yang lebih tajam
Untuk O(sqrt(N)), grafik akan melengkung di kiri atas, sehingga semakin besar N, grafik semakin mendatar.
Untuk O(log N), grafik akan melengkung di kiri atas juga tetapi cepat semakin mendatar grafiknya.
Untuk O(2^N), grafiknya akan menjijikan langsung menuju ke atas
Untuk O(N!), grafiknya akan lebih menjijikan daripada 2^N
Untuk O(N^N), grafiknya akan kelihatan, well, mending jangan dilihat bisa kena serangan jantung
Untuk lebih jelasnya aku dah ngegoogling supaya lebih make sense maksudnya...



Mungkin sementara ini dulu, takut dah kepanjangan, ini cuman gambaran kasar apa itu Big O Notation sama kompleksitas.
Artikel ini gak sampai sini... Ini belum berakhir!!!
Jangan kamu kira kamu sudah menang, aku bakal kembali!!! *niru pelem2...

Ciao~...