Agustus 27, 2010

Big O Notation (Notasi Big O)

Big O Notation adalah notasi atau cara penulisan kompleksitas sebuah program. misalnya program tersebut di ulang dengan "for" sebanyak N kali, maka kompleksitasnya adalah O(N).
berikut contohnya

i:=0;
while i<N do
begin
  i:=i+1;
  //statement;
end;

Tapi dalam penulisan Big O ada syarat penulisan, salah satunya adalah "tidak boleh menyertakan konstanta dalam penulisannya".
Contoh

i:=0;
while i<N do
begin
  i:=i*2;
  //statement;
end;

sebenarnya kompleksitas code diatas O(2Log N), namun karena big O tuh mempunyai syarat "konstanta tidak di hitung" maka 2Log N ditulis O(Log N). maka code diatas di tulis O(Log N).
Contoh lagi



i:= -2;
while i<N do
begin
  i:=i+1;
  //statement;
end;

kompleksitas potongan program yg di atas itu adalah O(N+2). tapi menurut aturan penulisan big O, itu hanya di tulis O(n) karena konstanta tidak perlu di tulis.

kenapa konstanta tidak perlu di tulis ?
karena konstanta dapat dihitung dan biasanya tidak mendekati tak hingga. bandingkan dengan N yg nilai nya mungkin saja bisa meledak hingga limit mendekati tak hingga. sedangkan konstanta nilai nya sudah terbatas.
contoh lagi

i:=0;
while i<N do
begin
  i:=i+1;
  j:=0;
  while j<N do
  begin
     j:=j+1;
     //statement;
  end;
end;

Code diatas memiliki O(N2) karena memiliki double looping.
contoh lagi

i:=0;
while i<N do
begin
  i:=i+1;
  j:=0;
  while j<N do
  begin
     j:=j+1;
     k:=0;
     while k<N do
     begin
        k:=k+1;
        //statement;
     end;
  end;
end;

Sudah tau dong apa jawabannya. yap. O(N3). karena program diatas memiliki triple looping.

untuk info lebih lanjut. tanya pak wikipedia, buka aja link yang ini ya.
http://en.wikipedia.org/wiki/Big_O_notation

Jadi kirakira begitu lah Big O notation, jika ada kesalahan mohon maaf karena kurakura sendiri pun kurang mengerti tentang Big O notation. Ohya, sebagai bocoran, kurakura akan membahas macammacam kompleksitas dan kecepatannya. Sekian posting kurakura, jika ada kesalahan kurakura mohon maaf.


Source : Post by drw_di-ar (kurakuraprogrammer) at Forum Olimpiade.org

Bye. Selamat Berpuasa bagi yang Melaksanakan.
salam kurakura :)
Wrote by kurakuraprogrammer
Labels: ,

6 komentar:

  1. MMufidLuthfi29 Agustus 2010 pukul 20.50

    udah dicoba tapi blum terlalu paham !!!

    ada yang lebih details g ?

    BalasHapus
  2. Unknown25 November 2012 pukul 14.53

    mantab nih.. thanks penjelasannya bro :)

    BalasHapus
  3. Unknown4 April 2013 pukul 08.10

    bagaimana kalau soalan dye seperti ini..
    for (i = n; i>0 ; i--) {
    cout<<”hello”;
    }
    adakah Jawapan T(n)= O(n)?? masih konfius ..

    BalasHapus
    Balasan
    1. Handrie Noprisson10 April 2015 pukul 11.15

      Setau saya itu juga O(N) sebab perulangan terjadi sebanyak n kali dengan nilai n yang terus berkurang hingga <= 0.

      Hapus
  4. Unknown1 Juni 2016 pukul 11.25

    Terima kasih, sedikit bingung sama penjelasan wiki :) At least... Yang ini lebih jelas buat saya...

    BalasHapus
  5. Unknown1 Juni 2021 pukul 09.36

    Kalau untuk mengatahui Big O Forward Chaining ?
    function PL-FC-ENTAILS? (KB, Q) returns True or False
    inputs: KB, the knowledge base, a set of propositional definite clauses q, the query, a proposition symbol count  a table, where count( e] is the number of symbols in c's premise inferred  a table, where inferred[s] is initially false for all symbols agenda  a queue of symbols, initially symbols known to be true in KB
    while agenda is not empty do
    p  PoP(agenda)
    if p = q then return true
    if inferred[p]= false then
    inferred[p]  true
    for each clause c in KB where p
    is in c.PREMISE do
    decrement count[c]
    if count[c] = 0 then
    add
    c.CONCLUSION to agenda
    return false

    BalasHapus

Langganan: Posting Komentar (Atom)