Big O Notation ဆိုတာဘာလဲ

Computer ကျောင်းဆင်းတွေဆိုရင်တော့ Big O ဆိုတာဘာလဲသိကြမယ်ထင်တယ်။ ကျွန်တော်တော့ ကိုယ့်ဘာသာ Algorithm Courses တွေလိုက်တက်ရင်းဟိုဖတ်ဒီဖတ်ဖတ်ရင်းမှ Big O ဆိုတာကြားဖူးပြီးလေ့လာဖြစ်တာပါ။ ကျွန်တော့်အတွက်တော့စလုပ်ခါစမှာ သိပ်မလွယ်ဘူးလို့ခံစားရပါတယ်။ ကျွန်တော်တက်နိုင်သလောက် အလွယ်ကူဆုံးဖြစ်အောင်တော့ကြိုးစားပြီး References တွေယူပြီးရှင်းပြထားပေးပါတယ်။

Big O ဆိုတာဘာလဲကအရင်စလိုက်ကြရအောင်။ ရိုးရိုးရှင်းရှင်းနားလည်အောင်ပြောရမယ်ဆိုရင် Big O ဆိုတာ Programmer အချင်း Algorithm တွေအကြောင်းပြောတဲ့နေရာမှာသုံးတဲ့စကားဖြစ်ပါတယ်။ Algorithm ထပ်ရှင်းရမယ်ဆိုရင် ကျွန်တော်တို့ရေးနေတဲ့ Function တွေဟာ Algorithm တွေလို့အကြမ်းဖျင်းမှတ်သားနိုင်ပါတယ်။ အဲ့တော့ Big O ဆိုတာ ကျွန်တော်တို့ရေးသားနေတဲ့ Program ထဲက Function တွေက input size ပေါ်မူတည်ပြီးတော့နှေးတယ်မြန်တယ်ဆိုတာတွေကိုခွဲခြားပေးတဲ့နည်းလို့ သတ်မှတ်နိုင်ပါတယ်။ နောက် Big O ကိုတစ်နည်း Asymptotic Notation လို့ခေါ်ပါတယ်။

မှတ်ချက်။ ကျွန်တော်ဒီ Blog Post မှာတော့ Big O ရဲ့ Mathematical Formal Definition ကိုရှုပ်သွားမှာစိုးလို့မရှင်းပြတော့ပါဘူး။ နောက်ထက် Post တစ်ခုလုပ်ပြီးရှင်းပြဖို့ကြိုးစားပါ့မယ်။

O(1) time (or “constant time”)

အောက်က Function တစ်ခုနှင့်စမ်းလိုက်ကြရအောင်…

function printFirstItem(items) {
  console.log(items[0]);
}

အထက်ဖော်ပြပါ Function ကိုတစ်ချက်ကြည့်မယ်ဆိုရင် items ထဲက values တွေဘယ်လောက်ဘဲတိုးလာတိုးလာ ဒီ Function ရဲ့ complexity က O(1) ဘဲဖြစ်ပါတယ်။

O(1) function

အထက်ဖော်ပြပါ ပုံဟာ O(1) run time ဖြစ်တဲ့အတွက်ဘယ်လောက်ဘဲ Value တွေတိုးလာတိုးလာ အချိန်ကြာတာကတော့တူတူ (“constant time”) ဘဲဖြစ်နေပါလိမ့်မယ်။ O(1) constant time ဖြစ်တဲ့ Function ရဲ့ running time ကတော့ဘယ်လိုပြောရမလဲ the best ပေါ့နော် 🤣။

O(n) time (or “linear time”)

function printAllItems(items) {
  items.forEach(item => {
    console.log(item);
  });
}

ကျွန်တော်တို့အထက်ဖော်ပြပါ Code block ကိုကြည့်မယ်ဆိုရင် ဒီ Function ရဲ့ Run Time က O(n) (linear time) ပါ။ ဒီနေရာမှာ items ထဲက value တိုးလာတာနှင့်အမျှ Function ထဲက Process လုပ်တာကလည်းတဖြည်းဖြည်းတိုးလာမှာဖြစ်တဲ့အတွက် O(n) (linear time) ပေါ့။ သူ့ရဲ့ Run time က Big O(n) လောက်မမြန်တာတော့သေချာတယ်။ O(1) က the best ဆို O(n) က Good လို့ပြောရမယ်ထင်တယ်။

O(n) runtime

O(n^2) time (“quadratic time”)

function printAllPossibleOrderedPairs(items) {
  items.forEach(firstItem => {
    items.forEach(secondItem => {
      console.log(firstItem, secondItem);
    });
  });
}

အထက်ဖော်ပြပါ Function ကိုကြည့်မယ်ဆိုရင် nested loop. Loop ထဲမှာ Loop ပြန်ပတ်ထားတယ်။ ကျွန်တော်တို့ items ဆိုတဲ့ array ထဲမှာ n items ရှိတယ်ဆိုရင် အပြင်ဘက်က Loop က n time နောက်အတွင်းပိုင်း loop က n time ကြာမယ် စုစုပေါင်းဒီ Function ရဲ့ Running time က O(n^2)။ O(n^2) က O(1) တို့ O(n) တို့နှင့်ယှဥ်ရင်တော့ Shitty ဖြစ်တယ်လို့ပြောရမှာဘဲ 🤣။ အောက်ဖော်ပြပါ O(n^2), O(n), O(1) Running Time နှိုင်းယှဥ်ချက် Graph ကိုတစ်ချက်ကြည့်ကြည့်လိုက်ရအောင်။

O(n^2), O(n), O(1) Running Time နှိုင်းယှဥ်ချက် Graph

အခုကျွန်တော်ရှင်းပြဖို့ကျန်နေသေးတာကတော့ O(log n) ဘဲ။ သူကဒီတိုင်းရှင်းပြရတာနည်းနည်းရှုပ်လို့ Merge Sort တို့ Binary Search တို့အကြောင်းပြောပြမှသူကိုအသေးစိတ်ပြန်ရှင်းပြတော့မယ်။

ဒီလောက်ဆိုရင် Big O ဆိုတာဘာလဲသိသွားလောက်ပါပြီ။ အခုဆို ကိုယ်ရေးထားတဲ့ Code ထဲမှာ O(n^2) Nested loop တွေများပါမလား… O(n) ရအောင်လုပ်လို့ရမလား… ဒါမျိုးလေးတွေတွေးနိုင်သွားပါပြီ။ နောက်ပိုင်း Algorithm တွေ Data Structure တွေရဲ့ Running Time အကြောင်းပြောတဲ့အခါမှာလည်းအသုံးပြုသွားနိုင်ပြီလို့ထင်ပါတယ် 😎။

ကြမ်းကိုးများ

Asymptotic Notation Best explanation

Leave a Reply

Up Next:

Hexadecimal number system ဆိုတာဘာလဲ

Hexadecimal number system ဆိုတာဘာလဲ