6 May 2020
Link 1=>Why Big O? Gentle Introduction
Big O ဆိုတာ (English အက္ခရာ အိုပါ တချို.က zero နဲ.မှားရေးတာမြင်ဖူးလို.) ဘာလဲ ဘာလို.သုံးလဲဆိုတာလေး အကြမ်းဖျင့်ပေါ့ misconception တွေကိုရှင်းပြချင်တာပါ။
Big O ဆိုတာ Algorithm တွေရဲ. complexity ကိုတိုင်းတဲ့ နည်းတခုပါ။ ဒီနေရာမှာ algorithm တွေလို.ပြောပါတယ် program လို.မပြောပါဘူး သေချာကြည့်ပါ။
Algorithm နဲ. Program နဲ.ဘာကွာတာလဲလို.မေးရင် (ဒီနေရာဖို.ပေါ့) ဉပမာ ကျနော်တို.က sorting algorithm တခုကို ဘယ်သူကပိုကောင်းလဲဆိုတာ သိချင်တယ် ကိုယ့် application မှာ ဘယ်ကောင့်ကိုသုံးရမလဲ ချိန်ချင်တယ်၊ ဒါဆို Algorithm တခုတည်းကို ရေးမယ် Pentinum I , RAM 128 MB တလုံးပေါ်မှာ run မယ် နောက်တလုံးမှာကျတော့ Core i7, RAM 8 GB အပေါ်မှာ run မယ် ဘယ်သူက ပိုမြန်မယ်ထင်ပါသလဲ။
Core i7, RAM 8GB အပေါ်မှာ run တဲ့ကောင်က machine spec ပိုကောင်းတဲ့အတွက် သူကပိုမြန်မှာပေါ့ running time milisecond နဲ.ထုတ်ကြည့်လိုက်ရင်။ ဒါဆို ခုနက စမ်းတာသည် algorithm ၁ ခုတည်းကိုတောင် machine spec သာတဲ့ကောင်က မြန်တယ်ဆိုတဲ့အဖြေထွက်နေတယ်။ အဲ့တော့ အဲ့နည်းနဲ. algorithm တွေကို တိုင်းလို.ရမလားဆိုတော့ မရနိုင်ဘူးပေါ့။
ဒါကြောင့် ဘာကိုသုံးလဲဆိုတော့ algorithm analysis က Math သုံးပြီး algorithm တွေရဲ. complexity ကိုတိုင်းတယ်၊ ဒီနေရာမှာ complexity မှာ အဓိက၂မျိုးရှိတယ် Space Complexity, Time Complexity .
Space Complexity ဆိုတာက ဒီ algorithm ကိုသုံးရင် memory requirement ဘယ်လောက်ယူသလဲဆိုတာကိုပြောတာ။ Time complexity ဆိုတာ algorithm ရဲ. running time ကိုတွက်တာ။ ဉပမာ database implementation မှာလုပ်မဲ့ algorithm တွေဆိုရင် space ရော time ရောပါ ထဲ့တွက်ရတာမျိုးရှိမယ်။
အဲ့တော့ Big O ဆိုတာ ဘာအတွက်သုံးတာလဲ လို. အတိုချုံ.ပြန်ပြောရရင် hardware, machine spec တွေအပေါ်မမူတည်ပဲနဲ.ဘယ် algorithm သည် ဘယ်လောက် complexity ရှိတယ်ဆိုတာကို တိုင်းတဲ့နည်းလို.ဆိုရမှာပါ။ ဘာကြောင့် hardware, machine spec အပေါ်တိုင်းတာသည် မတိကျဘူးဆိုတာ အပေါ်မှာ ရေးထားပြီးသားပါ။
ခုနက Complexity ကိုတိုင်းတဲ့အခါမှာ ဘယ်အပေါ်မူတည်ပြီး တွက်သလဲဆိုတော့ input size အပေါ်မူတည်ပြီး တွက်ပါတယ်။ ဉပမာ ကျတော်တို.က အခန်း 10 ခုရှိတဲ့ array ကို sort လုပ်မယ်ဆိုပါစို. ဒါဆိုရင် input size n သည် 10 ပါ။ သူ.အပေါ်မူတည်ပြီး ဘယ် sorting algorithm သည် အကောင်းဆုံး ဖြစ်မလဲဆိုတာကို ရွေးလို.ရပါတယ်။
ဉပမာ sorting algorithm ၁ က သူ.ရဲ. time complexity က O(n) ဆိုပါစို. Sorting algorithm ၂ က O(n^2) ဆိုပါစို. ဒီနေရာမှာ n နဲ. n^2 ဘယ်သူက များသလဲဆိုတော့ n^2 က များပါတယ် ဒါဆိုကျတော်တို.က generally O(n) ဖြစ်တဲ့ကောင်ကို ရွေးရမှာပါ။
O(n) ကို Order of n လို.ဖတ်ပါတယ်။ ဒီနေရာမှာ Order ဆိုတာဘာလဲဆိုတာ ရှင်းပြဖို.လိုပါတယ်။Big O notation သည် Math notation ပါ O သည် ဘာကိုတိုင်းတာလဲဆိုရင် upper bound ကိုတိုင်းတာပါ။ နားလည်လွယ်အောင် ရှင်းပြရရင် worst case scenario ကိုတိုင်းတာပါ၊
Worst Case scenario ဆိုတာလဲဆိုရင် ဉပမာ linear search ပေါ့ O(n) ရှိမယ်
[1,6,7,8,9,11]
linear search ဆိုတာ array ခန်းကို 0 ကနေ စပြီးတော့ မတွေ.မချင်း ဆုံးအတဲ့အထိရှာသွားတဲ့ algorithm မျိုးကိုပြောတာပါ။ pseudo code အရဆို ဒီလိုပေါ့
for(int I=0; I< arr.length ;I++)
{
if( arr[I] == key)
{
index = I;
break;
}
}
အပေါ်က input size သည် 6 ဖြစ်ပါတယ်၊ အဲ့မှာ 1 ကိုရှာမယ်ဆိုရင် loop သည် တခေါက် run ပြီး ပြီးသွားမှာပါ။ best case scenairo လို.ခေါ်ပါတယ်။ တကယ်လို.များ မရှိတဲ့ကောင်ကိုရှာမယ် ဒါမှမဟုတ် နောက်ဆုံးမှာရှိတဲ့ element ကိုရှာရမယ်ဆိုရင် array ခန်းမပြီးမချင်းကိုရှာရမှာပါ ဒါဆို loop ကို n ကြိမ် run ရပါမယ်၊ ဒါကို worst case scenario လို.ခေါ်ပါတယ် O(n) သည် worst case scenario ကိုတွက်တပါ။
ဆိုချင်တာက Big O notation နဲ.သုံးပြီးဆိုရင် algorithm တွေရဲ. worst case complexity ကိုတွက်တာပါ၊ Algorithm သည် input size အပေါ်မှာ ဘာတွေလုပ်ရတယ် ဆိုတဲ့ step ကိုတွက်တာပါ။ ဒီနေရာမှာ အဓိက ယူရမှာသည် for loop ပါ ဘာလို.ဆိုတော့ input size အပေါ်မူတည်ပြီးတွက်လို.ပါ။ for loop ထဲက code တွေသည် step ပါ၊
တွက်နည်းကတော့ ဘာသာရပ်တခုအနေနဲ.သက်သက်ရှိပါတယ် analysis of algorithm လို.ခေါ်ကြပါတယ်။
အနှစ်ချုပ်ပြောရရင် Big O သည် algorithm တွေရဲ. input size ပေါ်မူတည်ပြီး လုပ်ရတဲ့ step တွေဘယ်လောက်များလဲဆိုတာကို worst case scenario အပေါ်မူတည်ပြီးတွက်တာပါ။
SPM' Notes 