22 Aug 2023
How to compute Big(O)
Big(O) အကြောင်းအရင်က ဒီမှာရေးဖူးတယ်၊ ခုကဘယ်လိုတွက်မလဲပေါ့၊ အကုန်လုံးတော့မပြောနိုင်ဘူး။ အဆင်ပြေသလောက်ပေါ့၊
https://web.facebook.com/thet.khine.587/posts/10214139966572694
Big O သည် ဘယ်အပေါ်မူတည်ပြီး တွက်ရတာလဲဆိုတော့ input size, input size ဆိုတာ ဆိုချင်တာက sorting စီမယ်ဆိုပါစို. ဒါဆို sorting စီမဲ့ data structure ရဲ. total အရေအတွက် အဲ့ကောင်ကို n လို.ထားတယ်ဆိုပါစို.ဥပမာ contact list 100 ရှိတယ် ဒါဆို n=100 Big O မှာကျတော့ n ရဲ. real value သည်သိပ်အသုံးမတည့်လှဘူး။ ဆိုချင်တာက algorithm သည် input size အပေါ်မှာ complexity ဘယ်လောက်ကုန်မယ်ဆိုတာကိုပဲ တွက်တာပေါ့။
Example တွေပုံတွေကအဆင်ပြေတဲ့စီကနေ မလာတာ။ အောက်က Graph မယ် O(n) ကို ဆွဲပြထားတယ် အပေါ်တက်သွားရင် cost ပိုကြီးတယ်ပေါ့၊ O(n) သည် O(1) ထက်ပိုကြီးတယ်ပေါ့၊ O(n) ဆိုတာ input size အပေါ်မူတည်ပြီး n ကြိမ် လုပ်ရတယ်ပေါ့၊
ဒီနေရာမှာ အကြိမ်ဆိုတာကို ဘယ်လိုရေလဲဆိုတော့ input size အပေါ် processing လုပ်ရတဲ့ ဟာကို ရွေတွက်ရတာပါ။
O(1)
input size ဘယ်လောက်ကြီးကြီး ဘယ်လောက်များများ တကြိမ်ပဲလုပ်ရတဲ့အတွက်သူ.ကို constant လို.ခေါ်တယ်။ ဥပမာ array တခုထဲက first element ကိုလိုချင်တယ်ဆိုပါစို. ဒါဆို
arr[0] ဒီလိုယူရမယ်မဟုတ်လား ဒါဆို input arr အပေါ်မှာ operation တခုပဲလုပ်ရတဲ့အတွက် O(1) ရမယ်။ အောက်က function လိုမျိုးပေါ့။
function getFirst(arr)
{
return arr[0];
}
O(n)
အောက်က example ကိုကြည့်ရအောင်
array တခုလုံးမှာရှိတဲ့ element တွေအကုန်ထုတ်ချင်တယ်ဆိုပါစို. ။
function printAll(arr)
{
for(let i=0;i< arr.length;i++)
{
console.log(arr[i]);
}
}
အဲ့ဒီမှာ input ပေါ်ကို computation လုပ်တာဆိုတဲ့ အဆင့်သည်
console.log(arr[i]); သူပေါ့.
သူ.ကို ဘယ်နှခါလုပ်ရမလဲဆိုရင် for loop အရ 0 ကနေ arr.length ထက်ငယ်တဲ့အထိဆိုတော့ n ကြိမ်သွားရတယ်ပေါ့ အဲ့တော့သူသည် O(n) ပေါ့။ ဥပမာ Linear search သည် O(n) ပေါ့ သူ.အဓိက search code သည် worst case မှာ n ကြိမ်လုပ်ရတယ်ပေါ့။
O(n^2)
ဥပမာ array တခုရှိတယ်ဆိုပါစို. [‘A’,’B’,’C’] ပေါ့သူတို.ရဲ. all possible pair ကိုလိုချင်တယ်
ဒါမျိုးပေါ့
AA,
AB,
AC etc ပေါ့ ဒါဆိုရင် ဒီလိုရေးရမယ်။
function allPair(arr)
{
for(let i=0;i< arr.length;i++)
{
for(let j=0;j< arr.length;j++)
{
console.log(arr[i]+”+arr[j]);
}
}
}
အဓိက ကျတဲ့ input ကို process လုပ်တဲ့ code သည် ဒီ code
console.log(arr[i]+”+arr[j]);
သူ.ကို loop ၂ ထပ်ပတ်ထားတယ် i loop နဲ. j loop အဲ့မှာ တခုစီက n စီဆိုတော့ nested loop အရေအတွက်သည် outer loop * inner loop ဒါဆို n*n သည် n^2 ရမယ်။
O(c^n)
အောက်က fibonacci ထုတ်တဲ့ code example ပေါ့ (အကောင်းဆုံး implementation မဟုတ်ဘူး O(c^n) ကိုဥပမာပြဖို.ပဲ)
public int fibonacci(int number) {
if (number <= 1) {
return number;
} else {
return fibonacci(number – 1) + fibonacci(number – 2);
}
}
အဲ့မှာ သူက
return fibonacci(number – 1) + fibonacci(number – 2);
သည်အသက် fibonacci ကို ၂ခါ ခေါ်တယ် recursive ခေါ်တယ်ပေါ့။
fibonacci သည် recursive မှာ n ကြိမ် run တယ် <=1 ဆိုပြန်မယ် မဟုတ်ရင် -1 ဆိုတော့ n ကြိမ်ပေါ့ အဲ့တော့ ၂ ခါကို n ကြိမ်ဆင့်ခေါ်ရတော့ 2^n ပေါ့။
O(log n)
သူက binary search example ကိုသုံးရမှာ ဒီမှာသာသွားကြည့်တော့.
https://web.facebook.com/thet.khine.587/posts/10209990933049449
Binary search မှာ array ကို တဝက်စီခွဲတယ်ပြီးတော့ ပိုင်းရှာတယ် အဲ့လိုရှာနိုင်ဖို. array သည် sorted လုပ်ပြီးသားဖြစ်ဖို.လိုတယ်။အဲ့တော့ သူ. complexity သည် O(log n) ဖြစ်တယ်။
ဒီနေရာမှာ log ကိုရှင်းပြဖို.လိုတယ် 2^3 သည် 8 ဆိုပါစို. ဒါဆို 8 ဖြစ်အောင် 2 ကိုဘယ်၂ခါမြှောက်ရလဲဆိုတာကိုတွက်ချင်ရင် log2(8) ဆိုပြီး တွက်ရမယ် ဒါဆို 2*2*2 ဖြစ်တဲ့အတွက် log2(8) သည် 3 ရမယ် log သည် power ဆန်.ကျင်ဘက်သဘောပေါ့ ဒီနေရာမှာ 2 သည် base လို.ပြောရမယ် computer programming မှာ Big O တွက်ရင် base 2 နဲ.ပဲတွက်တယ် အဲ့တခုသတိထားရမယ်။
နောက် Big O တွက်တဲ့အခါ constant တွေ insignificant term တွေ drop လုပ်ရတာမျိုးရှိသေးတယ် သက်သက် အကျယ်တဝင့်ကို လိုက်လေ့လာပေါ့။
Original link=>(https://m.facebook.com/story.php?story_fbid=pfbid02hksg6Mh3MtS4oQH3Bnh2mtosyqXFT7QSPkiDxQDAUNcHtJVn9yqvFCCcAFQpfHCSl&id=1819241055&mibextid=Nif5oz)
SPM' Notes 