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) 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^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(log n) ဘဲ။ သူကဒီတိုင်းရှင်းပြရတာနည်းနည်းရှုပ်လို့ Merge Sort တို့ Binary Search တို့အကြောင်းပြောပြမှသူကိုအသေးစိတ်ပြန်ရှင်းပြတော့မယ်။
ဒီလောက်ဆိုရင် Big O ဆိုတာဘာလဲသိသွားလောက်ပါပြီ။ အခုဆို ကိုယ်ရေးထားတဲ့ Code ထဲမှာ O(n^2) Nested loop တွေများပါမလား… O(n) ရအောင်လုပ်လို့ရမလား… ဒါမျိုးလေးတွေတွေးနိုင်သွားပါပြီ။ နောက်ပိုင်း Algorithm တွေ Data Structure တွေရဲ့ Running Time အကြောင်းပြောတဲ့အခါမှာလည်းအသုံးပြုသွားနိုင်ပြီလို့ထင်ပါတယ် ?။
O(log n) အကြောင်းကို ဒီမှာ ဖတ်နိုင်ပါပြီ။
ကြမ်းကိုးများ