Data Structure နှင့် Big-O Complexity အပိုင်း (၂)

ကုဒ်တွေရဲ့ စွမ်းဆောင်ရည်ကို သုံးသပ်တဲ့အခါ ထည့်သွင်းစဉ်းစားရမယ့် အချက် ၂ ချက်ရှိပါတယ်။ Time Complexity နဲ့ Space Complexity ပါ။ လွယ်လွယ်ပြောရရင် Time Complexity ဆိုတာ ကုဒ်ကိုတွက်ချက်ဖို့ အချိန် ဘယ်လောက်ယူရသလဲကို ရည်ညွှန်းတာဖြစ်ပြီး Space Complexity ကတော့ Memory ထပ်ဆောင်း ဘယ်လောက်များများ လိုအပ်သလဲဆိုတာကို ရည်ညွှန်းပါတယ်။ တိတိကျကျပြောရရင် Time Complexity ဆိုတာ ထည့်ပေးလိုက်တဲ့ Data အရွယ်အစားပေါ်မူတည်ပြီး Algorithm ရဲ့ တွက်ချက်ဖို့ လိုအပ်မယ့်အချိန်ပမာဏဖြစ်ပါတယ်။ အလားတူစွာပဲ၊ Space Complexity ဆိုတာ ထည့်ပေးလိုက်တဲ့ Data အရွယ်အစားပေါ်မူတည်ပြီး Algorithm ရဲ့ တွက်ချက်ဖို့လိုအပ်မယ့် Memory ပမာဏဖြစ်ပါတယ်။

ကျနော်တို့ဟာ ရေးသားထားတဲ့ကုဒ်တွေကို တတ်နိုင်သမျှ Memory ပမာဏ အနည်းဆုံးနဲ့မြန်မြန်ဆန်ဆန် အလုပ်လုပ်ဖို့သာ လိုချင်ကြတာဖြစ်ပါတယ်။ ဒါပေမယ့် လက်တွေ့မှာ ကျနော်တို့ရဲ့ကုဒ်တွေဟာ ထည့်ပေးလိုက်ရတဲ့ Data အရွယ်အစား (Input Size) ၊ တွက်ချက်ပေးမယ့် စက်၊ သွင်ပြင်လက္ခဏာပေါ်မူတည်ပြီး အလုပ်လုပ်ဆောင်နိုင်စွမ်းကွာခြားသွားပါတယ်။ မတူညီတဲ့ Input အရွယ်အစား တခုချင်းစီအတွက် ကုဒ်ရဲ့ Performance ကို တိုင်းတာလို့ရနိုင်ပေ့မယ့် တကယ်တမ်း ဘယ်လို Input အရွယ်အစားဖြစ်နေပါစေ၊ ယေဘုယျကျကျ ဆုံးဖြတ်ပေးနိုင်မယ့် တိုင်းတာမူမျိုး လိုအပ်ပါတယ်။ ဒီနေရာမှာ Big-O ပါဝင်လာရပါပြီ။

နမူနာကြည့်ရအောင်ပါ။ ကျနော်တို့ရေးသားထားတဲ့ကုဒ် (တနည်းအားဖြင့် Function တခု သို့မဟုတ် Algorithm တခု) က Input အဖြစ် ကိန်းတခုကို ရယူပြီး ဂဏန်း (Digit) ဘယ်နှစ်လုံးပါဝင်သလဲ တွက်ထုတ်ပေး နိုင်မယ်ဆိုပါစို့။ ထည့်သွင်းလိုက်တဲ့ကိန်းက 3415 ဖြစ်ခဲ့ရင် ဂဏန်း (Digit) အရေအတွက်ဟာ 4 လုံးဆိုပြီး ရရှိမှာဖြစ်ပါတယ်။ ထည့်သွင်းလိုက်တဲ့ကိန်းက 241,539 ဖြစ်ခဲ့ရင် ဂဏန်းအရေအတွက်ဟာ 6 လုံးဆိုပြီး ရရှိမှာ ဖြစ်ပါတယ်။ ဒီသဘောတရားကို လေ့လာလိုက်ရင် တွက်ချက်ပေးရတဲ့ လုပ်ဆောင်မှု အကြိမ်အရေအတွက်ဟာ ထည့်သွင်းလိုက်တဲ့ ကိန်းပမာဏနဲ့ တိုက်ရိုက်သက်ဆိုင်နေတာကို တွေ့ရမှာဖြစ်ပါတယ်။ ကိန်းပမာဏ များလာတဲ့အပေါ်လိုက်ပြီး ဂဏန်းအရေအတွက်ကို တွက်ထုတ်ရတာဖြစ်ပါတယ်။ တနည်းအားဖြင့် ကိန်းတန်ဖိုး ကြီးလာလေ၊ တွက်ချက်လုပ်ဆောင်ရတဲ့ အကြိမ်ရေ ပိုများလာလေဖြစ်ပါတယ်။ ထည့်သွင်းလိုက်တဲ့ ကိန်းအရွယ်အစားနဲ့ တွက်ချက်လုပ်ဆောင်ရတဲ့ အကြိမ်အရေအတွက်ကို ဂရပ်တခုအဖြစ် ရေးဆွဲလိုက်ရင် မျဉ်းဖြောင့်အတိုင်း ၄၅ ဒီဂရီထောင်တတ်သွားတဲ့ပုံစံ (Linear Growth) ကိုမြင်တွေ့ရမှာဖြစ်ပါတယ်။

နောက်ထပ် နမူနာကုဒ်တခုကို ထပ်စဉ်းစားပါမယ်။ ကျနော်တို့ရဲ့ကုဒ်က Input အဖြစ် ကိန်းတခုကို ရယူပြီး စုံကိန်း၊မကိန်း ခွဲခြားပေးနိုင်တယ်ဆိုပါစို့။ ကိန်းတခုဟာ စုံကိန်းဟုတ်မဟုတ်၊ မကိန်းဟုတ်မဟုတ် ခွဲခြားနိုင်ဖို့ လုပ်ရမယ့်အလုပ်က အဲဒီကိန်းရဲ့ နောက်ဆုံး ဂဏန်း (Last Digit) ကို ကြည့်ပြီး တွက်ချက်မှုအနည်းငယ် ပြုလုပ်လိုက်ရုံပါပဲ။ ဒီနေရာမှာဆိုရင် ထည့်ပေးလိုက်တဲ့ကိန်းက ဘယ်လောက်ကြီးတယ်ဆိုတာ အရေးမပါတော့ပါဘူး။ ကျနော်တို့လုပ်ရတဲ့ အလုပ်က ကိန်းရဲ့ နောက်ဆုံး ဂဏန်း (Last Digit) လေးကိုပဲ စစ်ဆေးပြီး တွက်ချက်ဆုံးဖြတ်လို့ရနိုင်ပါတယ်။ တွက်ချက်မှုဟာ ကိန်းရဲ့အရွယ်အစားပေါ် မမူတည်တော့ပါဘူး။ ဆိုတော့ ဒီတွက်ချက်မူဟာ မပြောင်းလဲတဲ့တွက်ချက်မှုအကြိမ်အရေတွက် လိုအပ်တယ်လို့ မှတ်ယူနိုင်ပါတယ်။ ဂရပ်တခုအဖြစ် ရေးဆွဲလိုက်ရင် အလျားလိုက် ရေပြင်ညီ မျဉ်းဖြောင့်တခုကို မြင်တွေ့ရမှာဖြစ်ပါတယ်။ ဒီဂရပ်ကို Constant Growth လို့ခေါ်ပါတယ်။

Big-O င်္သကေတဆိုတာ မတူညီတဲ့ Input Size တွေအတွက် ကျနော်တို့ ကုဒ်တွေဟာ အဆိုးဆုံးအခြေအနေမှာ ဘယ်လောက်အထိတွက်ချက်လုပ်ဆောင်ရသလဲဆိုတာ ဖော်ပြပေးနိုင်တဲ့ င်္သချာနည်းဆိုင်ရာဖော်ပြချက်ဖြစ်ပါတယ်။ Big-O င်္သကေတဟာ Algorithm ရဲ့ Performance ကို သက်ရောက်နိုင်မယ့် တကယ်တမ်း အရေးပါတဲ့ Factor တွေပေါ်မှာပဲ တွက်ချက်ထားတာဖြစ်ပါတယ်။

အပေါ်မှာ ပြောခဲ့တဲ့ Linear Growth အခြေအနေကို ဖော်ပြမယ့် Big O င်္သကေတဟာ O(n) ဖြစ်ပါတယ်။ Constant Growth ကို ဖော်ပြမယ့် င်္သကေတက O(1) ဖြစ်ပါတယ်။

Big-O ရဲ့ O ကို "Order of" လို့ခေါ်ပါတယ်။ Algorithm ရဲ့ Growth Rate ကို ဖော်ပြပါတယ်။ တွက်ချက်ဖို့ ဘယ်လောက် အချိန်ကြာနိုင်သလဲ၊ Memory ဘယ်လောက်ယူသလဲ စသည်ဖြင့်ပါ။

n က တနည်းအားဖြင့် Argument ပါ၊ အဆိုးဆုံးအခြေအနေမှာ တွက်ချက်လုပ်ဆောင်ရမယ့် အကြိမ်အရေအတွက်ကို ကိုယ်စားပြုပါတယ်။

ဥပမာ၊ Big-O င်္သကေတက O(n) ဖြစ်တယ်ဆိုရင် ဆိုလိုတာက ကျနော်တို့ကုဒ်ရဲ့ Time သို့မဟုတ် Space လိုအပ်ချက်ဟာ Input အရွယ်အစားပေါ်မူတည်ပြီး (Linear Growth) မျဉ်းဖြောင့်အတိုင်း ထောင်တတ်သွားနိုင်တယ်လို့ ဆိုလိုတာဖြစ်ပါတယ်။ Input Size သာ နှစ်ဆတိုးသွားခဲ့ရင် Time သို့ Space လိုအပ်ချက်ဟာလည်း နှစ်ဆတိုးသွားမှာ ဖြစ်ပါတယ်။ အဲသလိုပဲ Big-O င်္သကေတက O(n^2) ဖြစ်တယ်ဆိုရင် Algorithm ရဲ့ Time သို့မဟုတ် Space လိုအပ်ချက်ဟာ Input Size ပေါ်မူတည်ပြီး နှစ်ထပ်ကိန်းတန်ဖိုးတိုးတိုးလာမှာဖြစ်ပါတယ်။ Input Size နှစ်ဆတိုးသွားခဲ့ရင် Time သို့ Space လိုအပ်ချက်ဟာ လေးဆတိုးသွားမှာ ဖြစ်ပါတယ်။

အပေါ်မှာ ပြောခဲ့သလို Big-O င်္သကေတဟာ Algorithm ရဲ့ Performance ကို သက်ရောက်နိုင်မယ့် တကယ်တမ်း အရေးပါတဲ့ Factor တွေပေါ်မှာပဲ တွက်ချက်ထားတာဖြစ်ပါတယ်။ Linear Growth ကို နမူနာအနေနဲ့ကြည့်ပါ။ O(2n), O(n+5), O(4n-2) စသည်ဖြင့် ထပ်ပေါင်း n ရဲ့တန်ဖိုးဟာ အရေးမကြီးပါဘူး။ တကယ်တမ်း O(n) အဖြစ်အနေနဲ့ ယူဆသွားမှာဖြစ်ပါတယ်။ နမူနာ Linear ဂရပ်မှာ ကြည့်ပါ။ (နမူနာ ဂရပ်တွေကို PDF version မှာ ဖတ်ရှုနိုင်ပါတယ်။) O(2^n) နဲ့ O(n) ရဲ့ကွာခြားမူဟာ Infinity Input Size မှာဆိုရင် ထည့်သွင်းစဉ်းစားဖို့မလိုသလောက် တနည်းအားဖြင့် အရေးမပါသလောက်ဖြစ်သွားမှာဖြစ်ပါတယ်။

Big-O င်္သကေတတွေနဲ့ သူတို့ရဲ့ အဓိပ္ပာယ်ကို ဖော်ပြပေးပါမယ်။

O(1) – Constant Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့မဟုတ် Space ဟာ ကိန်းသေပမာဏအဖြစ် မပြောင်းမလဲရှိနေမှာကို ရည်ညွှန်းပါတယ်။ ဆိုလိုတာက Input Size ဘယ်လောက်ပဲကြီးလာပါစေ တွက်ချက်ရတဲ့ Complexity က မပြောင်းလဲဘဲ တစ်သမတ်တည်း ရှိနေမှာဖြစ်ပါတယ်။ ဥပမာ၊ Array ရဲ့ Element တခုကို Index ထောက်ပြီး ခေါ်ယူတဲ့အခြေအနေမျိုးတွေ၊ အပေါ်မှာဖော်ပြခဲ့တဲ့ စုံကိန်း၊ မကိန်း တွက်ချက်တဲ့အခြေအနေတွေဖြစ်ပါတယ်။

O(log n) – Logarithmic Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့မဟုတ် Space ဟာ သေးငယ်တဲ့ပမာဏလောက်သာ ပြောင်းလဲသွားမှာကို ရည်ညွှန်းပါတယ်။ ဆိုလိုတာက Input Size နှစ်ဆတိုးသွားရင် တွက်ချက်ရတဲ့အကြိမ်အရေအတွက် Complexity က အနည်းငယ်လောက်သာ တိုးလာမှာဖြစ်ပါတယ်။ ဥပမာ၊ Binary Search လိုမျိုးဖြစ်ပါတယ်။

O(n) – Linear Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့မဟုတ် Space ဟာ (Linear Growth) မျဉ်းဖြောင့်အတိုင်း ထောင်တတ်ပြောင်းလဲသွားမှာကို ရည်ညွှန်းပါတယ်။ ဆိုလိုတာက Input Size နှစ်ဆတိုးသွားရင် တွက်ချက်ရတဲ့အကြိမ်အရေအတွက် Complexity ကလည်း နှစ်ဆတိုက်ရိုက်တိုးလာမှာဖြစ်ပါတယ်။ ဥပမာ၊ Array တခုပေါ်မှာ Iterating လုပ်တဲ့အခါမျိုးတွေဖြစ်ပါတယ်။

O(n log n) - Linearithmic Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့ Space ဟာ Linear Growth Rate ထက် အနည်းငယ် ပိုမြန်ပြီး ပြောင်းလဲသွားမှာကို ရည်ညွှန်းပါတယ်။ Merge-sort တို့၊ Quick-sort တို့လို Sorting Algorithm တွေမှာ တွေ့ရတတ်ပါတယ်။

O(n^2) - Quadratic Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့ Space ဟာ နှစ်ထပ်ကိန်းတန်ဖိုး တိုးတိုးလာမှာကို ဆိုလိုတာဖြစ်ပါတယ်။ Bubble-sort တို့၊ Selection Sort တို့လို Algorithm တွေမှာ တွေ့ရတတ်ပါတယ်။

O(2^n) - Exponential Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့ Space ဟာ ထပ်ကိန်းတန်ဖိုး တိုးတိုးလာမှာကို ဆိုလိုတာဖြစ်ပါတယ်။ ဒီအခြေအနေဟာ ပုံမှန်အားဖြင့် တော်တော်လေး Inefficient မဖြစ်တဲ့အခြေအနေအဖြစ် မှတ်ယူနိုင်ပါတယ်။

O(n!)—Factorial Complexity: ဒီသင်္ကေတဟာ Input Size ပေါ်မူတည်ပြီး Time သို့ Space ဟာ Factorial တန်ဖိုး တိုးတိုးလာမှာကို ဆိုလိုတာဖြစ်ပါတယ်။ Input Size နှစ်ဆတိုးသွားခဲ့ရင် Time သို့ Space လိုအပ်ချက်ဟာ ကြောက်ခမန်းလိလိ တိုးလာမှာ ဖြစ်ပါတယ်။ ဒါဟာ အဆိုးဝါးဆုံးအခြေအနေလို့ မှတ်ယူလို့ရမှာဖြစ်ပါတယ်။

•PDF version အပြည့်အစုံကို ဒီလင့်ခ်ကနေ ရယူနိုင်ပါတယ်။

https://drive.google.com/file/d/1oAir7eJ03b3nSURPQ5Y5ytbcCMdFKfHz/view?usp=sharing

#CodewithThura