Big-O Notation (algorithm ရဲ့ ကြာချိန် တိုးနှုန်းကို ပြတဲ့ သင်္ကေတ)

B2.4.1: Describe efficiency by calculating Big O to analyse scalability; time and space complexities; algorithm choice based on scalability and efficiency.
မြန်မာလို: scalability (ဒေတာ များလာတဲ့အခါမှာလည်း ကောင်းကောင်း ဆက်အလုပ်လုပ်နိုင်မှု) ကို ခွဲခြမ်းစိတ်ဖြာဖို့ Big O ကို တွက်ပြီး efficiency (ထိရောက်မှု) ကို describe (ဖော်ပြရှင်းပြ) လုပ်နိုင်ရပါမယ်။ ပါဝင်တာတွေက time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) နဲ့ space complexity (input ကြီးလာရင် memory လိုအပ်ချက် တိုးပုံ)၊ ပြီးတော့ scalability နဲ့ efficiency ကို အခြေခံပြီး algorithm (အယ်လ်ဂိုရီသမ်၊ ပြဿနာကို အဆင့်ဆင့် ဖြေရှင်းတဲ့ နည်းလမ်း) ကို ရွေးချယ်ခြင်း တို့ ဖြစ်ပါတယ်။

အဓိက အယူအဆများ

Big-O Notation ဆိုတာ ဘာလဲ

Algorithm တွေကို နှိုင်းယှဉ်တဲ့အခါ input size (program ထဲ ထည့်ပေးတဲ့ ဒေတာ ပမာဏ) ကြီးလာရင် သူတို့ရဲ့ စွမ်းဆောင်ရည် ဘယ်လို ပြောင်းလဲလဲဆိုတာကို ဖော်ပြနိုင်တဲ့ နည်းလမ်း တစ်ခု လိုပါတယ်။ Big-O notation က အဲဒါကို ပေးပါတယ်: input size n ကြီးလာတဲ့အခါ algorithm တစ်ခုရဲ့ ကြာချိန် ဒါမှမဟုတ် memory (မှတ်ဉာဏ်) ဘယ်လို တိုးလာလဲဆိုတာအတွက် upper bound (တိုးနှုန်းက ကျော်မသွားတဲ့ အထက်ဆုံး ကန့်သတ်ချက်) ကို ပေးပါတယ်။ Big-O ကို worst case (အဆိုးဆုံး အခြေအနေ) အတွက် အများဆုံး ပြောလေ့ ရှိပြီး best case (အကောင်းဆုံး အခြေအနေ) နဲ့ average case (ပျမ်းမျှ အခြေအနေ) အတွက်လည်း ဒီ သင်္ကေတကိုပဲ သုံးပါတယ်။ ဥပမာ bubble sort (ဘေးချင်းကပ် တန်ဖိုးတွေကို လဲပြီး စီခြင်း) ရဲ့ best case က O(n) ပါ။

Big-O က “Input size ကို နှစ်ဆ တိုးလိုက်ရင် ဒီ algorithm က ဘယ်လောက် ပိုကြာမလဲ” ဆိုတဲ့ မေးခွန်းကို ဖြေပေးပါတယ်။

Big-O က growth rate (input ကြီးလာရင် အလုပ် တိုးလာနှုန်း) ကို ဖော်ပြတာပါ၊ လုပ်ဆောင်ချက် အရေအတွက် အတိအကျကို ဖော်ပြတာ မဟုတ်ပါဘူး။ O(n) algorithm တစ်ခုက အဆင့် 3n + 5 ဆင့် ကြာနိုင်ပါတယ်။ ဒါပေမယ့် n အရမ်းကြီးလာတဲ့အခါ constant (ကိန်းသေ) တွေနဲ့ lower-order term (ထပ်ကိန်း နိမ့်တဲ့ အပိုင်း) တွေက သိပ်အရေးမပါတော့လို့ ဖယ်ထုတ်လိုက်ပါတယ်။ အရေးကြီးတာက တိုးလာပုံကို ပြတဲ့ မျဉ်းကွေးရဲ့ ပုံသဏ္ဌာန် ပါ။

အတွေ့ရများတဲ့ complexity class (တိုးနှုန်း အမျိုးအစား) များ

Big-O အမည် တိုးပုံ ဥပမာ
O(1) Constant (ကိန်းသေ) Input size ဘယ်လောက်ပဲ ဖြစ်ဖြစ် ကြာချိန် အတူတူပဲ Array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) element (အစုထဲက အချက်) တစ်ခုကို index (နေရာအမှတ်) နဲ့ ယူခြင်း: arr[5]
O(log n) Logarithmic (log n နှုန်းနဲ့ တိုးတဲ့) Input နှစ်ဆ ဖြစ်ရင် အဆင့် တစ်ဆင့်ပဲ တိုးတယ် Binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း): အဆင့်တိုင်းမှာ ဒေတာကို တစ်ဝက် လျှော့တယ်
O(n) Linear (n နဲ့ အချိုးကျ တိုးတဲ့) Input နှစ်ဆ ဖြစ်ရင် ကြာချိန်လည်း နှစ်ဆ Linear search (တစ်ခုချင်း ဆက်တိုက် ရှာနည်း): element တိုင်းကို စစ်တယ်
O(n log n) Linearithmic (n log n နှုန်းနဲ့ တိုးတဲ့) Linear ထက် နည်းနည်း ပိုဆိုးတယ် ထိရောက်တဲ့ sorting (အစဉ်တကျ စီခြင်း) algorithm တွေ၊ ဥပမာ merge sort (ဒေတာကို ခွဲစီပြီး ပြန်ပေါင်းတဲ့ နည်း) နဲ့ quicksort (pivot နဲ့ ခွဲပြီး မြန်မြန် စီတဲ့ နည်း) ရဲ့ average case
O(n²) Quadratic (နှစ်ထပ်ကိန်း နှုန်းနဲ့ တိုးတဲ့) Input နှစ်ဆ ဖြစ်ရင် ကြာချိန် လေးဆ Bubble sort၊ selection sort (အငယ်ဆုံးကို ရှာပြီး နေရာချ စီခြင်း): ဒေတာပေါ်မှာ nested loop (loop ထဲမှာ ထပ်ပါတဲ့ loop) တွေ ပတ်တယ်

တိုးနှုန်းတွေကို နှိုင်းယှဉ်ခြင်း

Big-O ဘာကြောင့် အရေးကြီးလဲ နားလည်ဖို့ input size ကြီးလာတဲ့အခါ ဒီ complexity class တွေ ဘယ်လို တိုးလာလဲ ကြည့်ပါ:

n O(1) O(log n) O(n) O(n log n) O(n²)
10 1 3 10 33 100
100 1 7 100 664 10,000
1,000 1 10 1,000 9,966 1,000,000
10,000 1 13 10,000 132,877 100,000,000
100,000 1 17 100,000 1,660,964 10,000,000,000

n = 100,000 မှာ O(n²) algorithm က လုပ်ဆောင်ချက် သန်းပေါင်း 10,000 (10 billion) လုပ်ရပြီး O(n log n) algorithm ကတော့ သန်း 1.7 (1.7 million) ခန့်ပဲ လုပ်ရပါတယ်: 6,000 ဆခန့် ပိုမြန်ပါတယ်။ အခုခေတ် hardware ပေါ်မှာဆိုရင် ဒီကွာခြားချက်က millisecond (တစ်စက္ကန့်ရဲ့ တစ်ထောင်ပုံ တစ်ပုံ) ပိုင်းအတွင်း ပြီးတဲ့ program နဲ့ စက္ကန့်ပိုင်းကနေ မိနစ်ပိုင်းအထိ ကြာတဲ့ program ကြားက ကွာခြားချက်ပါ။

အဖြစ်များတဲ့ အမှားတစ်ခုက O(n²) ကို O(n) ထက် နည်းနည်းလေးပဲ ပိုဆိုးတယ်လို့ ထင်တာပါ။ အပေါ်က ဇယားက နှစ်ခု ဘယ်လောက် ကွာသွားလဲ ပြပါတယ်: input ကို နှစ်ဆ တိုးလိုက်ရင် linear အလုပ်က နှစ်ဆခန့် တိုးပေမယ့် quadratic အလုပ်ကတော့ လေးဆ တိုးပါတယ်။ Input ကြီးတဲ့အခါ ဘယ် algorithm က လက်တွေ့ သုံးလို့ရလဲဆိုတာကို ဒီကွာခြားချက်က ဆုံးဖြတ်ပေးနိုင်ပါတယ်။ ဒါကြောင့် ကိုယ့်ဒေတာ အရွယ်အစားနဲ့ သင့်တော်တဲ့ algorithm ကို ရွေးပါ။

Time Complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ)

Time complexity က input size ကြီးလာတာနဲ့အမျှ algorithm တစ်ခု လုပ်ရတဲ့ လုပ်ဆောင်ချက် အရေအတွက် ဘယ်လို တိုးလာလဲဆိုတာကို တိုင်းတာပါတယ်။ သူက “ဒေတာ ကြီးလာရင် ဒါက ဘယ်လောက် ပိုကြာမလဲ” ဆိုတဲ့ မေးခွန်းကို ဖြေပေးပါတယ်။

Time complexity ကို လက်တွေ့မှာ မြင်ဖူးပြီးသားပါ:

  • Linear search က element တစ်ခုချင်းစီကို တစ်ခုပြီးတစ်ခု စစ်ပါတယ်။ Worst case မှာ (ရှာနေတဲ့ တန်ဖိုးကို မတွေ့တဲ့အခါ ဒါမှမဟုတ် အဲဒါက အဆုံးမှာ ရှိနေတဲ့အခါ) element n ခုလုံးကို စစ်ရပါတယ်။ Time complexity: O(n)။
  • Binary search က comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) တစ်ကြိမ်စီမှာ ကျန်နေတဲ့ element တွေရဲ့ တစ်ဝက်ကို ဖယ်ထုတ်ပါတယ်။ Element n ခုအတွက် comparison အများဆုံး အရေအတွက်က log₂ n ရဲ့ ဒဿမ အပိုင်းကို ဖယ်ပြီး 1 ပေါင်းထားတဲ့ တန်ဖိုးပါ (log₂ n ခန့်ပါ၊ element တစ်သန်းဆိုရင် 20 ကြိမ်)။ Time complexity: O(log n)။
  • Bubble sort က nested loop ကို သုံးပါတယ်: outer loop (အပြင်ဘက် loop) က n-1 ကြိမ် ပတ်ပြီး pass (ဒေတာကို တစ်ခေါက် ဖြတ်ကြည့်ခြင်း) တစ်ခါစီမှာ inner loop (အတွင်းဘက် loop) က n-1 ကြိမ်အထိ ပတ်ပါတယ်။ Time complexity: O(n²)။
  • Selection sort ကလည်း nested loop ကို သုံးပါတယ်: နေရာ n-1 ခု တစ်ခုချင်းစီအတွက် ကျန်နေတဲ့ unsorted (အစဉ်တကျ မစီရသေးတဲ့) element တွေကို ဖြတ်ကြည့်ပြီး အငယ်ဆုံး တန်ဖိုးကို ရှာပါတယ်။ Time complexity: O(n²)။

Space Complexity (input ကြီးလာရင် memory လိုအပ်ချက် တိုးပုံ)

Space complexity က input ဒေတာ ကိုယ်တိုင်အပြင် algorithm တစ်ခုက memory ဘယ်လောက် ထပ်လိုလဲဆိုတာကို တိုင်းတာပါတယ်။ သူက “ဒါက memory ဘယ်လောက် ထပ်လိုမလဲ” ဆိုတဲ့ မေးခွန်းကို ဖြေပေးပါတယ်။

  • Input size ဘယ်လောက်ပဲ ဖြစ်ဖြစ် variable (တန်ဖိုး သိမ်းထားတဲ့ နာမည်ပေးထားတဲ့ နေရာ) အနည်းငယ်ပဲ (temp၊ i၊ j လို) ထပ်သုံးတဲ့ algorithm ရဲ့ space complexity က O(1) ပါ: ထပ်လိုတဲ့ နေရာက ပုံသေပါ။
  • Input array တစ်ခုလုံးကို copy ကူးတဲ့ algorithm ရဲ့ space complexity က O(n) ပါ: ထပ်လိုတဲ့ memory က input size နဲ့ အချိုးကျ (linear) တိုးလာပါတယ်။

Bubble sort ရော selection sort ပါ in place (မူလ array ထဲမှာပဲ) စီပါတယ်: variable အနည်းငယ်ပဲ ထပ်သုံးပြီး မူလ array ကိုပဲ နေရာပြန်စီတာပါ။ သူတို့ရဲ့ space complexity က O(1) ပါ။

Iterative (တူညီတဲ့ အဆင့်တွေကို ထပ်ခါထပ်ခါ လုပ်တဲ့) ပုံစံနဲ့ ရေးထားတဲ့ binary search ကလည်း ထပ်လိုတဲ့ နေရာ O(1) ပဲ သုံးပါတယ်၊ low၊ mid နဲ့ high variable တွေပဲ လိုပါတယ်။

စာမေးပွဲမှာ algorithm တစ်ခုကို “evaluate” (အားသာချက်နဲ့ အားနည်းချက်တွေကို ချိန်ဆပြီး အကဲဖြတ်ပါ) လုပ်ခိုင်းရင် time complexity ရော space complexity ပါ နှစ်ခုလုံး ကို ဆွေးနွေးပါ။ Algorithm တစ်ခုက မြန်ပေမယ့် (time complexity ကောင်း) memory အများကြီး ထပ်လိုနိုင်ပါတယ် (space complexity မကောင်း)၊ ပြောင်းပြန်လည်း ဖြစ်နိုင်ပါတယ်။ အကောင်းဆုံး ရွေးချယ်မှုက အခြေအနေရဲ့ ကန့်သတ်ချက်တွေပေါ် မူတည်ပါတယ်။

Code ကနေ Big-O ကို တွက်ခြင်း

Code အပိုင်း တစ်ခုရဲ့ Big-O ကို သိဖို့ loop (ထပ်ခါထပ်ခါ run တဲ့ code အပိုင်း) တွေရဲ့ ဖွဲ့စည်းပုံ ကို ကြည့်ပါ:

Element n ခုပေါ်မှာ ပတ်တဲ့ loop တစ်ခုတည်း = O(n)

for (int i = 0; i < n; i++) {
    // constant-time operation
}

for i in range(n):
    # constant-time operation

Element n ခုပေါ်မှာ တစ်ခုစီ ပတ်တဲ့ nested loop များ = O(n²)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // constant-time operation
    }
}

for i in range(n):
    for j in range(n):
        # constant-time operation

ပတ်တိုင်း ဒေတာကို တစ်ဝက် လျှော့တဲ့ loop = O(log n)

int low = 0, high = n - 1;
boolean found = false;
while (low <= high && !found) {
    int mid = (low + high) / 2;
    // compare and adjust low or high
}

low = 0
high = n - 1
found = False
while low <= high and found == False:
    mid = (low + high) // 2    # // keeps mid a whole number (Java's int division does this automatically)
    # compare and adjust low or high

Loop မပါရင် (ဒါမှမဟုတ် ပုံသေ အကြိမ်အရေအတွက်ပဲ ပတ်တဲ့ loop တွေဆိုရင်) = O(1)

int first = arr[0];  // constant time
int last = arr[arr.length - 1];  // constant time

first = arr[0]              # constant time
last = arr[len(arr) - 1]    # constant time

Code ထဲမှာ sequential (တစ်ခုပြီးမှ တစ်ခု) လုပ်ဆောင်ချက်တွေ ပါရင် (loop တစ်ခုပြီးမှ နောက် loop တစ်ခု လာရင်) complexity တွေကို ပေါင်းပါ: O(n) + O(n) = O(n)။ Code ထဲမှာ nested (တစ်ခုထဲမှာ တစ်ခု) လုပ်ဆောင်ချက်တွေ ပါရင် (loop တစ်ခုထဲမှာ နောက် loop တစ်ခု ရှိရင်) မြှောက်ပါ: O(n) * O(n) = O(n²)။ ပေါင်းတဲ့အခါ higher-order term (ထပ်ကိန်း မြင့်တဲ့ အပိုင်း) က အဖြေကို ဆုံးဖြတ်ပါတယ်: O(n²) + O(n) = O(n²)။

မှန်ကန်တဲ့ algorithm ကို ရွေးခြင်း

ဘယ် algorithm ကို ရွေးမလဲဆိုတာ ဒေတာနဲ့ အခြေအနေပေါ် မူတည်ပါတယ်။ ဒီအချက်တွေကို စဉ်းစားပါ:

အချက် ပိုမြန်တဲ့ algorithm ကို ရွေးစေတဲ့ အခြေအနေ ပိုရိုးရှင်းတဲ့ algorithm ကို ရွေးစေတဲ့ အခြေအနေ
ဒေတာ အရွယ်အစား Dataset (ဒေတာ အစုအဝေး) ကြီးရင် ထိရောက်တဲ့ algorithm တွေ လိုတယ် Dataset သေးရင် ဘယ် algorithm နဲ့ပဲ ဖြစ်ဖြစ် မြန်မြန် run တယ်
ဒေတာ အစဉ် Sort လုပ်ပြီးသား ဒါမှမဟုတ် စီလုနီးပါး ဖြစ်နေတဲ့ ဒေတာက adaptive (ဒေတာ အခြေအနေနဲ့ လိုက်ပြီး မြန်နှုန်း ပြောင်းတဲ့) algorithm တွေကြောင့် အကျိုးရှိတယ် ကျပန်း ဒေတာမှာ ကွာခြားချက် နည်းတယ်
Memory ကန့်သတ်ချက် Memory နည်းတဲ့အခါ in-place algorithm တွေ (O(1) space) က ပိုကောင်းတယ် Memory လုံလောက်ရင် memory ထပ်သုံးတာ လက်ခံနိုင်တယ်
ရေးရတဲ့ ခက်ခဲမှု ပိုရှုပ်တဲ့ algorithm တွေမှာ bug (code ထဲက အမှား) ပါနိုင်တယ် ရိုးရှင်းတဲ့ algorithm တွေက ရေးရ၊ debug (program ထဲက အမှားကို ရှာပြီး ပြင်) လုပ်ရ ပိုလွယ်တယ်

ဆုံးဖြတ်ချက် ဥပမာ: ကျောင်းသား record (အချက်အလက် အများကြီး စုထားတဲ့ ဒေတာ တစ်ခု) 1 သန်း ပါတဲ့ sorted (တန်ဖိုးအလိုက် အစဉ်တကျ စီပြီးသား) array ထဲမှာ ID တစ်ခုကို ရှာဖို့ လိုတယ် ဆိုပါစို့။

  • Linear search: O(n) = comparison 1,000,000 ကြိမ်အထိ
  • Binary search: O(log n) = comparison အများဆုံး 20 ကြိမ်

ဒီမှာ binary search က မှန်ကန်တဲ့ ရွေးချယ်မှုဆိုတာ ထင်ရှားပါတယ်: 50,000 ဆခန့် ပိုမြန်ပါတယ်။ ဒါပေမယ့် binary search အတွက် array က sorted ဖြစ်နေရပါမယ်။ ဒေတာက unsorted ဖြစ်နေပြီး တစ်ကြိမ်ပဲ ရှာဖို့ လိုရင် အရင် sort လုပ်တာ (bubble sort နဲ့ဆိုရင် O(n²)၊ ထိရောက်တဲ့ sort နဲ့ဆိုရင် O(n log n)) နဲ့ binary search တစ်ကြိမ် ပေါင်းလိုက်တာက linear search တစ်ကြိမ်တည်းထက် ပိုနှေးနိုင်ပါတယ်။

တွက်ပြထားတဲ့ ဥပမာများ

ဥပမာ 1: Big-O ကို ခွဲခြားပါ

Code အပိုင်းလေး တစ်ခုချင်းစီရဲ့ time complexity ကို ဆုံးဖြတ်ပါ။

Code အပိုင်း A:

int sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum = sum + arr[i];
}

total = 0    # "sum" is a built-in function name in Python, so we use total instead
for i in range(len(arr)):
    total = total + arr[i]

အဖြေ: O(n)။ Element တစ်ခုစီကို တစ်ကြိမ်စီ ဝင်ကြည့်တဲ့ loop တစ်ခုတည်း ဖြစ်ပါတယ်။ လုပ်ဆောင်ချက် အရေအတွက်က array ရဲ့ အလျား (element အရေအတွက်) နဲ့ အချိုးကျ တိုးပါတယ်။

Code အပိုင်း B:

boolean hasDuplicate = false;
for (int i = 0; i < arr.length && !hasDuplicate; i++) {
    for (int j = i + 1; j < arr.length && !hasDuplicate; j++) {
        if (arr[i] == arr[j]) {
            hasDuplicate = true;
        }
    }
}

# Python's for loop cannot carry an extra condition, so the
# early-exit flag check moves into while loops instead.
has_duplicate = False
i = 0
while i < len(arr) and has_duplicate == False:
    j = i + 1
    while j < len(arr) and has_duplicate == False:
        if arr[i] == arr[j]:
            has_duplicate = True
        j = j + 1
    i = i + 1

အဖြေ: O(n²)။ Outer loop က n ကြိမ် ပတ်ပြီး inner loop က n-1 ကြိမ်အထိ ပတ်တဲ့ nested loop ပါ။ Inner loop က i + 1 ကနေ စတာကြောင့် comparison စုစုပေါင်းက n²/2 ခန့်အထိ လျော့သွားပေမယ့် Big-O notation မှာ constant factor (ကိန်းသေ မြှောက်ဖော်ကိန်း) ကို ဖယ်ထုတ်ပါတယ်။

Code အပိုင်း C:

System.out.println(arr[0]);
System.out.println(arr[arr.length - 1]);

print(arr[0])
print(arr[len(arr) - 1])

အဖြေ: O(1)။ သတ်မှတ်ထားတဲ့ array index တွေမှာ ရှိတဲ့ element တွေကို ယူတာက array အရွယ်အစား ဘယ်လောက်ပဲ ဖြစ်ဖြစ် ကြာချိန် ပုံသေ (constant-time) လုပ်ဆောင်ချက် ဖြစ်ပါတယ်။ Array မှာ element 10 ခု ရှိရှိ၊ 10 သန်း ရှိရှိ ဒီ code က လုပ်ဆောင်ချက် အရေအတွက် အတူတူပဲ လုပ်ပါတယ်။

ဥပမာ 2: Algorithm တွေကို နှိုင်းယှဉ်ခြင်း

ကျောင်းတစ်ကျောင်းက ကျောင်းသား record 50,000 ကို ကျောင်းသား ID အလိုက် စီထားတဲ့ array ထဲမှာ သိမ်းထားပါတယ်။ စနစ်က ကျောင်းသား တစ်ယောက်ရဲ့ record ကို ရှာဖို့ လိုပါတယ်။

Algorithm Time Complexity အများဆုံး လုပ်ဆောင်ချက် သင့်တော်လား
Linear search O(n) 50,000 ခဏခဏ ရှာရရင် နှေးတယ်
Binary search O(log n) ~16 မြန်ပြီး ထိရောက်တယ်

ခွဲခြမ်းစိတ်ဖြာချက်: Binary search မှာ comparison အများဆုံး log₂(50,000) = 16 ခန့်ပဲ လိုပါတယ်။ Linear search မှာတော့ comparison 50,000 ကြိမ်အထိ လိုနိုင်ပါတယ်။ တစ်စက္ကန့်အတွင်း အကြိမ်ကြိမ် ရှာရတဲ့ စနစ်အတွက် binary search က ထင်ရှားတဲ့ ရွေးချယ်မှု ဖြစ်ပါတယ်။

Space complexity: Algorithm နှစ်ခုလုံးက ထပ်လိုတဲ့ နေရာ O(1) ပဲ သုံးပါတယ်၊ index တွေနဲ့ target value (ရှာနေတဲ့ တန်ဖိုး) အတွက် variable အနည်းငယ်ပဲ လိုပါတယ်။ ဘယ်တစ်ခုမှ input size နဲ့ အချိုးကျ တိုးတဲ့ memory ထပ် မလိုပါဘူး။

Trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ): Binary search အလုပ်လုပ်ဖို့ array က sorted အတိုင်း ဆက်ရှိနေရပါမယ်။ ကျောင်းသား အသစ်တွေ ခဏခဏ ထည့်ရရင် ရှာတာ မြန်လာတဲ့ အကျိုးနဲ့အတူ sort လုပ်ထားတဲ့ အစဉ်ကို ထိန်းထားရတဲ့ ကုန်ကျစရိတ်ကိုပါ ထည့်စဉ်းစားသင့်ပါတယ်။

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. O(n²) time complexity ဆိုတာ ဘာကို ဆိုလိုသလဲ။

Q2. ဘယ် algorithm က O(log n) time complexity ရှိသလဲ။

Q3. O(1) space complexity ဆိုတာ ဘာကို ဆိုလိုသလဲ။

Q4. Code အပိုင်း တစ်ခုမှာ loop နှစ်ခု ပါပြီး တစ်ခုထဲမှာ တစ်ခု nested ဖြစ်နေပါတယ်။ Loop တစ်ခုစီက array ရဲ့ element n ခုလုံးကို ပတ်ပါတယ်။ သူ့ရဲ့ time complexity က ဘာလဲ။

Q5. O(n) algorithm တစ်ခုနဲ့ O(n²) algorithm တစ်ခု နှစ်ခုလုံးက item (အချက်) 10,000 ကို အလုပ်လုပ်ပါတယ်။ O(n²) algorithm က ခန့်မှန်းခြေ ဘယ်နှဆ ပိုနှေးသလဲ။

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

Code ပုံစံ တစ်ခုချင်းစီအတွက် loop ထဲမှာ run တဲ့ comparison ဒါမှမဟုတ် assignment (variable ထဲ တန်ဖိုး ထည့်ခြင်း) တွေကို လုပ်ဆောင်ချက်အဖြစ် ရေတွက်ပြီး Big-O complexity class ကို ခွဲခြားပါ။

Trace: လုပ်ဆောင်ချက်တွေကို ရေတွက်ခြင်း

Code ပုံစံnလုပ်ဆောင်ချက်Big-O
Loop တစ်ခုတည်း: for i = 0 to n-1 8
Nested loop: for i, for j = 0 to n-1 4
တစ်ဝက်စီ လျှော့တဲ့ loop: while n > 1, n = n/2 16
Array index နဲ့ element ကို ယူခြင်း: arr[0] 1000
တစ်ခုပြီးမှ တစ်ခု run တဲ့ loop နှစ်ခု: for i; for j (nested မဟုတ်) 5

n=16 ဖြစ်တဲ့ တစ်ဝက်စီ လျှော့တဲ့ loop အတွက်: 16 -> 8 -> 4 -> 2 -> 1၊ ဒါက loop 4 ပတ် ဖြစ်ပါတယ်။ log₂(16) = 4။

Spot the Error (အမှား ရှာခြင်း)

ကျောင်းသား တစ်ယောက်က အောက်က pseudocode ရဲ့ time complexity ကို ခွဲခြမ်းစိတ်ဖြာနေပါတယ်။ သူ့ ခွဲခြမ်းစိတ်ဖြာချက်မှာ အမှား တစ်ခု ပါနေပါတယ်။ အမှားပါတဲ့ line ကို ရွေးပါ၊ ပြီးရင် ပြင်နည်းကို ရွေးပါ။

1Loop 1: for i = 0 to n-1 → O(n) 2Loop 2: for j = 0 to n-1 → O(n) 3Loops are sequential, so total = O(n) * O(n) = O(n²) 4Space complexity: O(1). Only uses loop variables

Line 3 နဲ့ 4 က English စာတွေရဲ့ အဓိပ္ပာယ်: “Loops are sequential, so total” က loop တွေက sequential ဖြစ်လို့ စုစုပေါင်း၊ “Only uses loop variables” က loop variable တွေကိုပဲ သုံးတယ်လို့ အဓိပ္ပာယ်ရပါတယ်။

မှန်ကန်တဲ့ ခွဲခြမ်းစိတ်ဖြာချက်ကို ရွေးပါ:

Fill in the Blanks (ကွက်လပ် ဖြည့်ခြင်း)

Big-O complexity အနှစ်ချုပ်ကို ဖြည့်ပြီး ပြည့်စုံအောင် လုပ်ပါ။ အနှစ်ချုပ်ထဲက English စာတွေမှာ Time က time complexity၊ Space က space complexity၊ Key Rules က အဓိက စည်းမျဉ်းများ၊ inside က “ထဲမှာ”၊ then က “ပြီးရင်” လို့ အဓိပ္ပာယ်ရပါတယ်။

Algorithm Complexities
======================
Linear search:    Time = O()    Space = O()
Binary search:    Time = O()    Space = O()
Bubble sort:      Time = O()    Space = O()
Selection sort:   Time = O()    Space = O()

Key Rules
=========
Nested loops:     O(n) inside O(n) = O()
Sequential loops: O(n) then O(n) = O()

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ code က အတွင်းဘက်က လုပ်ဆောင်ချက် ဘယ်နှစ်ကြိမ် run သလဲ ရေတွက်ပါတယ်။ Loop နှစ်ခုလုံး ပြီးသွားတဲ့အခါ count မှာ ဘယ်တန်ဖိုး ရှိနေသလဲ။

int n = 4;
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}
System.out.println(count);

ဘာ print ထွက်လာမလဲ။

ဒီ code က တန်ဖိုး တစ်ခုကို 1 မရောက်ခင် တစ်ဝက် ဘယ်နှစ်ကြိမ် ခွဲလို့ရလဲ ရေတွက်ပါတယ်။ ဘာ print ထုတ်မလဲ။

int n = 32;
int count = 0;
while (n > 1) {
    n = n / 2;
    count++;
}
System.out.println(count);

ဘာ print ထွက်လာမလဲ။

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

  1. Complexity ကို ခွဲခြားပါ: အခြေအနေ တစ်ခုချင်းစီအတွက် time complexity က O(1)၊ O(log n)၊ O(n) ဒါမှမဟုတ် O(n²) ထဲက ဘယ်ဟာလဲဆိုတာ State (ဖော်ပြပါ):
    • (a) Array ထဲမှာ ကျောင်းသား တစ်ယောက်ရဲ့ အမှတ်ကို သူ့ index နဲ့ ရှာကြည့်ခြင်း
    • (b) Mailbox ထဲက email တိုင်းကို spam (မလိုလားအပ်တဲ့ အမှိုက် email) ဟုတ်မဟုတ် စစ်ခြင်း
    • (c) အက္ခရာစဉ်အတိုင်း စီထားတဲ့ အဘိဓာန်ထဲမှာ အလယ်ကနေ ဖွင့်ပြီး ရှာမယ့် အပိုင်းကို တဖြည်းဖြည်း ကျဉ်းအောင် လုပ်ကာ စကားလုံး တစ်လုံး ရှာခြင်း
    • (d) ကျောင်းသား တစ်ယောက်ချင်းစီရဲ့ စာမေးပွဲ အမှတ်ကို တခြား ကျောင်းသား တိုင်းရဲ့ အမှတ်နဲ့ နှိုင်းယှဉ်ခြင်း

  2. Growth rate ဇယား: n = 10၊ 100၊ 1,000 နဲ့ 10,000 ဖြစ်တဲ့အခါ O(n)၊ O(n log n) နဲ့ O(n²) အတွက် လုပ်ဆောင်ချက် အရေအတွက်ကို ပြတဲ့ ဇယား တစ်ခု ဆွဲပါ။ ဘယ် input size ရောက်တဲ့အခါ O(n) နဲ့ O(n²) ကြားက ကွာခြားချက်က သိသိသာသာ ဖြစ်လာသလဲ။

  3. Algorithm နှိုင်းယှဉ်ချက်: စာကြည့်တိုက် တစ်ခုမှာ အက္ခရာစဉ်အတိုင်း စီထားတဲ့ စာအုပ် 100,000 ရှိပါတယ်။ စာအုပ် တစ်အုပ်ကို ရှာဖို့ linear search သုံးတာနဲ့ binary search သုံးတာကို Compare (နှစ်ခုလုံးကို ထည့်ပြီး တူတာနဲ့ ကွာတာကို ဖော်ပြပါ)။ Algorithm တစ်ခုစီမှာ လိုမယ့် comparison အများဆုံး အရေအတွက်ကို State လုပ်ပြီး ဘယ်ဟာကို သုံးသင့်လဲ အကြံပြုပါ။

Extension (တိုးချဲ့ အဆင့်)

  1. ဒီ code ကို ခွဲခြမ်းစိတ်ဖြာပါ: အောက်က pseudocode (program ပုံစံ ရိုးရိုးစာနဲ့ ရေးတဲ့ algorithm) ရဲ့ time complexity နဲ့ space complexity ကို Determine (ဖြစ်နိုင်တဲ့ အဖြေ တစ်ခုတည်းကို ရှာထုတ်ပါ)။ Loop တစ်ခုစီက ဘာလုပ်လဲ ရှင်းပြပြီး သင့်အဖြေကို Justify (ဘာကြောင့် ရွေးတာလဲ အကြောင်းပြချက်နဲ့ ပြပါ)။ 
    for i = 0 to n-1
    for j = i+1 to n-1
        if arr[i] > arr[j]
            swap arr[i] and arr[j]
  2. Trade-off ခွဲခြမ်းစိတ်ဖြာချက်: Item (အချက်) 500 ပါတဲ့ dataset တစ်ခုကို 10,000 ကြိမ် ရှာဖို့ လိုပါတယ်။ နည်းလမ်း နှစ်ခုကို Compare လုပ်ပါ: (a) unsorted ဒေတာကို အကြိမ်တိုင်း linear search နဲ့ ရှာခြင်း၊ (b) ဒေတာကို selection sort နဲ့ အရင် sort လုပ်ပြီး ရှာတိုင်း binary search ကို သုံးခြင်း။ နည်းလမ်း တစ်ခုစီအတွက် လုပ်ဆောင်ချက် စုစုပေါင်း ခန့်မှန်းခြေကို Calculate (တွက်တဲ့ အဆင့်တွေကို ပြပြီး ဂဏန်း အဖြေ ရှာပါ) လုပ်ပြီး ပိုကောင်းတဲ့ နည်းလမ်းကို အကြံပြုပါ။

Challenge (စိန်ခေါ်မှု အဆင့်)

  1. Algorithm ဒီဇိုင်းကို အကဲဖြတ်ခြင်း: Social media platform တစ်ခုက user profile 10 သန်း သိမ်းထားပါတယ်။ Username (အသုံးပြုသူ အမည်) နဲ့ ရှာလို့ရတဲ့ စနစ် တစ်ခုကို Design (အစီအစဉ် ဒါမှမဟုတ် model တစ်ခု ရေးဆွဲပါ) လုပ်ပါ။ Profile အသစ်တွေ ခဏခဏ ထပ်ထည့်နေပြီး ရှာတာကလည်း အမြဲတမ်း ဖြစ်နေတယ်ဆိုတာကို ထည့်စဉ်းစားပြီး profile တွေကို sorted အတိုင်း ထားတာ (binary search အတွက်) နဲ့ unsorted ထားတာ (linear search အတွက်) ကြားက trade-off တွေကို Evaluate လုပ်ပါ။

  2. Best case၊ worst case နဲ့ average case: swapped flag (တစ်ခုခု ဖြစ်ခဲ့လား true/false နဲ့ မှတ်ထားတဲ့ အမှတ်အသား) နဲ့ optimise လုပ်ထားတဲ့အခါ bubble sort ရဲ့ best-case time complexity က ဘာကြောင့် O(n) ဖြစ်ပြီး worst case မှာ ဘာကြောင့် O(n²) ဖြစ်လဲဆိုတာ Explain (ရှင်းပြပါ)။ ဘယ်လို input ဒေတာက case တစ်ခုစီကို ဖြစ်စေလဲဆိုတာ Describe (ဖော်ပြရှင်းပြပါ)။ Input ဒေတာ ဘယ်လိုပဲ ဖြစ်ဖြစ် selection sort က ဘာကြောင့် O(n²) အမြဲ ကြာသလဲ။

ဆက်စပ် ခေါင်းစဉ်များ

  • အရင် သိထားရမှာများ: Searching Algorithms (ရှာဖွေရေး algorithm များ): linear search O(n) နဲ့ binary search O(log n) တို့က complexity class တွေရဲ့ လက်တွေ့ ဥပမာတွေပါ
  • အရင် သိထားရမှာများ: Sorting Algorithms (ဒေတာကို အစဉ်လိုက် စီတဲ့ algorithm များ): bubble sort O(n²) နဲ့ selection sort O(n²) တို့က quadratic growth (n² နှုန်းနဲ့ တိုးတာ) ကို ပြပါတယ်
  • ဆက်စပ်တာ: 1D Arrays (တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစု): algorithm အများစု အလုပ်လုပ်တဲ့ data structure (ဒေတာ သိမ်းဆည်းပုံ) က array ပါ၊ array ထဲက element ကို ယူတာက O(1) ပါ
  • နောက်ပိုင်း: Recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း)၊ HL (Higher Level: IB သင်တန်းမှာ ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အဆင့်) အတွက်ပါ။ Recursive algorithm တွေမှာ complexity ကို ခွဲခြမ်းစိတ်ဖြာတဲ့ ကိုယ်ပိုင် ပုံစံတွေ ရှိပါတယ် (ဥပမာ quicksort ရဲ့ average case O(n log n))

© EduCS.me. ကွန်ပျူတာသိပ္ပံ ပညာရေးအတွက် အရင်းအမြစ်တွေ စုထားတဲ့ နေရာပါ။ EduCS is an independent educational resource. It is not affiliated with, or endorsed by, the International Baccalaureate Organization. (EduCS ဟာ သီးခြား ပညာရေး အရင်းအမြစ်တစ်ခုပါ။ International Baccalaureate Organization နဲ့ ဆက်စပ်မှု မရှိသလို သူတို့ရဲ့ ထောက်ခံချက်လည်း မရှိပါဘူး။) ဆက်သွယ်ရန်

Built with Just the Docs.