BigO (Big Oh) Notation

ThutaMinThway — Sun, 21 Jul 2024 07:43:10 +0000

သာမန်တွေးကြည့်ရင် ကျွန်တော်တို့အသုံးပြုနေတဲ့ device တွေရဲ့ specification ပေါ်မူတည်ပြီး ဘယ်ဟာက မြန်တယ်၊ မမြန်ဘူး စမ်းကြည့်လို့ရနိုင်ပါတယ်။ ဒါပေမဲ့လည်း algorithm တစ်ခုကိုတိုင်းတာဖို့ ဒီလိုစမ်းကြည့်လို့မရသေးပါဘူး။

BigO Notation (Big Oh Notation) ဆိုတာ input size ဘယ်လောက်ရှိသလဲပေါ်မူတည်ပြီး algorithm ရဲ့ complexity ကို တိုင်းတာတာပါ။ Complexity မှာ အဓိကအားဖြင့် time နဲ့ space complexity ဆိုပြီး ၂မျိုးရှိတယ်။

Space Complexity
ပြသာနာ တစ်ခုကိုရှင်းဖို့ algorithm / program ကိုသုံးရင် memory ဘယ်လောက်ယူလဲကို ဆိုလိုတာပါ။

Time Complexity
Algorithm ရဲ့ run-time ဘယ်လောက်ရှိသလဲကို တွက်တာ။

BigO ကို တွက်တဲ့နေရာမှာ common complexities တွေ ရှိတယ်။

Constant | O(1) — Excellent/Best (constant time တစ်ကြိမ်ပဲလုပ်ရတဲ့အတွက် input size ဘယ်လောက်ရှိလည်း တွက်ရမယ့် calculation က အရေးမကြီးတော့ဘူး)
Logarithm | O(log n) — Good (Calculation ကို တစ်ဝက်စီပိုင်းပိုင်းပြီးလုပ်ဆောင်ရတာ)
Linear | O(n) — Fair (Algorithm တစ်ခုကို single loop လုပ်ပြီး linear time နဲ့ရှာရတာ)
O(n log n) — Bad (log linear complexity | binary sorting algorithm တွေမှာသုံးမယ်)
O(n²), O(2^n) and O(n!) — Horrible/Worst (Quadratic , Exponential time complexity ဖြစ်ပြီး loop after loop လုပ်တယ်)

...

*O(1) — Constant
*
Constant time တစ်ကြိမ်ပဲလုပ်ရတဲ့အတွက် algorithm တစ်ခုကို တွက်တဲ့နေရာမှာ input size က အရေးမကြီးတော့ပါဘူး။ ဥပမာပေးရရင် array တစ်ခုရှိတယ်။ Array ထဲမှာ element တွေအများကြီးရှိတယ်။ ဒါပေမယ့် ပထမဆုံး element ကိုလိုချင်တယ်ဆိုရင်…

`const names = ['thuta', 'john', 'christ', 'tony' ...]

console.log(names[0]) // get first element "thuta"`

O(log n) — Logarithm
Logarithm time | O(log n) သည်လည်းပဲ run-time မှာ input size ဘယ်လောက်ဖြစ်ဖြစ် depend မဖြစ်ပေမယ့် input size တစ်ဝက်ကိုတော့ depend ဖြစ်မှာပါ။ ဆိုလိုချင်တာက complexity တွက်တဲ့ step တစ်ဆင့်ချင်းစီမှာ input size က တစ်ဝက်စီ လျော့ကြသွားမှာဖြစ်တယ်။ ဥပမာပေးရရင် binary search ပါ။ Binary search အလုပ်လုပ်ပုံက sorting လုပ်ထားပြီးသား array တစ်ခုရှိမယ်။ Array ထဲမှာ ကိုယ်လိုချင်တဲ့ value ကိုရှာမယ်ဆိုရင် array length ကို တစ်ဝက်အရင်ပိုင်း။ ပြီးရင် ဆက်ရှာ။ ဒီလိုနဲ့ လိုချင်တဲ့ target ရောက်အောင်ထိသွားရမှာပါ။

numbers = [1,2,3,4,5,6,7,8,9] // target value is 2 first = 1 last = 9 mid = (first + last) / 2 = (1 + 9) / 2 = 5

ဒီနေရာမှာ အလယ်ဖြစ်တဲ့နေရာက 5 ။ လိုချင်တဲ့ value က 2။ ဒီတော့ sorting array ဖြစ်တဲ့အတွက် လိုချင်တဲ့ value နေရာကို ခန့်မှန်းလို့ရတာပေါ့။ ဒီတော့ ၅ ကနေစပြီး ညာဘက်က element တွေမဖြစ်နိုင်တော့ဘူးဆိုတော့ array ဆက်တွက်မယ်။

numbers = [1,2,3,4] // target value is 2
  first = 1
   last = 4
    mid = (first + last) / 2
        = (1 + 4) / 2 
        = 5 / 2 = 2 // target has reached

ဒါဆိုရင် လိုချင်တဲ့အဖြေရဖို့ ၂ဆင့်ပဲ တွက်စရာလိုတယ်။

O(n) — Linear
Linearly သွားတာဖြစ်တဲ့အတွက် input size များလေလေ algorithm run-time များလာလေလေ။

ဥပမာပေးရရင် array တစ်ခုရှိတယ်။ element 1 ကနေ 10 ထိရှိတယ်။

const array = [1,2,3,4,5,6,7,8,9,10] 

for (let i = 0; i <= array.length; i ++) {
    console.log('Hello world') // output will be 11 times of "Hello World"
}

ဒီတော့ ကိုယ်ပေးလိုက်တဲ့ n times အလိုက် အလုပ်လုပ်မယ်။ နောက် example ကြည့်ရအောင်

const calcFactorial = (n) => {
  let factorial = 1;
  for (let i = 2; i <= n; i++) {
    factorial = factorial * i;
  }
  return factorial;
};

console.log(calcFactorial(5)); // 120

5 * 4 * 3 * 2 * 1 = 120 ။ ဆိုတော့ ကျွန်တော်က calcFactorial မှာ input 10 ပေးရင်လည်း

10 * 9 * 8 * … ဒီလို linearly ဆက်သွားလိမ့်မယ်။

O(n²) — Quadratic

ကျွန်တော်တို့မှာ locker 5 ခုရှိတယ်။ သော့ ၅ ခုရှိတယ်။ ကျွန်တော်လိုချင်တဲ့ ပစ္စည်းက locker 5 ခုထဲက တစ်ခုမှာထည့်ထားတယ်။ ဒါပေမယ့် ကျွန်တော်က ပစ္စည်းရှိတဲ့နေရာလည်းမသိဘူး။ ဘယ်သော့နဲ့ ဘယ် locker နဲ့ match ဖြစ်လည်းဆိုတာလဲ မသိပြန်ဘူး။ ဆိုတော့ ကျွန်တော်က သော့၅ခုနဲ့ locker ၅ ခုကိုဖွင့်ရပါတော့မယ်။ ဒီလိုဆို 5 * 5 (5²) ပေါ့။

ဆိုလိုချင်တာက quadratic မှာ input size ထည့်ပြီး လိုချင်တဲ့ targeted value ရဖို့ loop 2 ခါပတ်ရတယ် (n times n) ဒါကြောင့်ဒီအခြေအနေက worst ဖြစ်နေရတာ။ Sample code ကြည့်မယ်ဆိုရင် pair ရှာတဲ့ example မျိုး။

function processPairs(array) {
  const n = array.length;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const pair = [array[i], array[j]];
      console.log("Processing pair:", pair);
    }
  }
}

const exampleArray = [1, 2, 3, 4];
console.log("Input array:", exampleArray);

processPairs(exampleArray); 

//output

[ 1 , 2 , 3 , 4 ]

[ 1 , 1 ] , [ 1 , 2 ], [ 1 , 3 ], [ 1 , 4 ]

[ 2 , 1 ] , [ 2 , 2 ], [ 2 , 3 ], [ 2 , 4 ]

[ 3 , 1 ] , [ 3 , 2 ], [ 3 , 3 ], [ 3 , 4 ]

[ 4 , 1 ] , [ 4 , 2 ], [ 4 , 3 ], [ 4 , 4 ]

O(2^n) — Exponential

Exponential time complexity ဆိုတာ input size တိုးသလောက် algorithm ရဲ့ run-time ကလည်း exponential ratio နဲ့ တိုးပွားတာ ဖြစ်တယ်။ ဒီလိုကိစ္စတွေမှာ loop တစ်ခုပြီးတစ်ခု nested လုပ်ထားရုံတင်မကပဲ recursive algorithm တွေမှာ တွေ့ရတတ်တယ်။

ဥပမာ binary decision tree တစ်ခုကို traverse လုပ်တာမျိုး၊ အောက်ပါ function မှာ recursive call တွေတွေ့ရမှာ ဖြစ်တယ်။ ဒီမှာ n က 2 ဖြစ်တဲ့အခါ base case ကိုရောက်ဖို့ 2² = 4 times ခေါ်ရမယ်၊ n က 3 ဖြစ်ရင် 2³ = 8 times ခေါ်ရမယ်။

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)); // Output: 5

O(n!) — Factorial
Factorial time complexity ကတော့ input size n ရဲ့ factorial value နဲ့ညီတဲ့ run-time ဖြစ်တယ်။ ဒီအခြေအနေမှာ run-time က အရမ်းမြင့်တက်တတ်တာကြောင့် practical ဖြစ်လို့အသုံးချဖို့အရမ်းခက်ပါတယ်။

ဥပမာ၊ permutation တွေကို generate လုပ်တဲ့ algorithm တစ်ခုမှာ ကြည့်မယ်ဆိုရင် input size n ရဲ့ permutations အားလုံးကို generate လုပ်ဖို့ n! operations လိုအပ်ပါတယ်။

function generatePermutations(array) {
    const results = [];

    function permute(arr, memo = []) {
        let cur, memoArr;
        for (let i = 0; i < arr.length; i++) {
            cur = arr.splice(i, 1);
            if (arr.length === 0) {
                results.push(memo.concat(cur));
            }
            permute(arr.slice(), memo.concat(cur));
            arr.splice(i, 0, cur[0]);
        }
        return results;
    }

    return permute(array);
}

console.log(generatePermutations([1, 2, 3])); 
// Output: All permutations of [1, 2, 3]

ဒီတော့ BigO Notation ဟာ input size ကြီးသွားလို့ algorithm ရဲ့ efficiency ဘယ်လိုပြောင်းလဲသလဲဆိုတာကိုရှင်းပြတယ်။ Run-time က input size ပေါ်မူတည်ပြီး ဘယ်လိုသက်ရောက်မှုရှိလဲဆိုတာနားလည်ဖို့ BigO ကိုသုံးတယ်။

DEV Community: ThutaMinThway

BigO (Big Oh) Notation