Big-O Notation — Growth Rate ကို တိုင်းတာခြင်း

နားလည်ထားရမယ့် အချက်

Big-O notation ဟာ algorithm တစ်ခုရဲ့ cost — time သို့မဟုတ် memory — ဟာ input size n ကြီးလာတာနှင့်အမျှ ဘယ်လိုကြီးထွားလာလဲဆိုတာကို ဖော်ပြတာဖြစ်ပြီး၊ laptop ပေါ်မှာ literal second ဘယ်လောက်ကြာလဲဆိုတာကို ဖော်ပြတာ မဟုတ်ပါဘူး။ ဒီကွာခြားချက်က အရေးကြီးတာက raw second ဟာ CPU speed, language, ဒီနေ့ system load ပေါ်မူတည်နေပြီး n နှစ်ဆတိုးလာရင် (သို့) ထောင်ဆတိုးလာရင် algorithm ဘယ်လိုပြုမူလဲဆိုတာ ဘာမှမပြောနိုင်ဘူး — growth rate ဟာ scale ဖြစ်တဲ့အခါ တကယ်ခန့်မှန်းပေးနိုင်တဲ့ property ဖြစ်ပါတယ်။ Big-O က constant factor တွေနှင့် lower-order term တွေကို တမင်ရည်ရွယ်ပြီး လျစ်လျူရှုပါတယ် — operation 3n+100 လုပ်တဲ့ algorithm တစ်ခုနှင့် n ပဲ လုပ်တဲ့ algorithm တစ်ခု နှစ်ခုစလုံးဟာ O(n) ဖြစ်ပါတယ်၊ ဘာလို့လဲဆိုတော့ n တစ်ခုအထက်ကျရင် constant multiplier က curve မြင့်တက်မှုနှုန်းနှင့်စာရင် အရေးမပါတော့လို့ပါ။ ရှုးခြားအောင်းရေး (best ကနေ worst) ordered common class တွေကတော့ O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, နှင့် O(n²) quadratic တို့ဖြစ်ပါတယ်။ function တစ်ခုရဲ့ complexity ကို ခန့်မှန်းဖို့ nested loop နှင့် lookup တွေကို ရေတွက်ပါ — n item တွေကို တစ်ကြိမ်ဖြတ်သွားတာက O(n); loop ထဲမှာ loop တစ်ခု n အတွက် ထည့်လိုက်ရင် O(n²); dictionary (သို့) set lookup တစ်ခုက item ဘယ်နှစ်ခုပါလဲမကြည့်ဘဲ O(1) ဖြစ်ပါတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ search feature က result တွေကို rank လုပ်တဲ့အခါ O(n log n) sort တစ်ခုနှင့် မတော်တဆ O(n²) ဖြစ်သွားတဲ့ sort (ဥပမာ naive bubble sort သို့မဟုတ် ထပ်ခါထပ်ခါ linear re-scan) ကြားက ကွာခြားချက်ဟာ lesson အနည်းငယ်ကို ချက်ချင်း rank လုပ်နိုင်တာနှင့် catalog က lesson ထောင်ချီရှိလာတဲ့အခါ page freeze ဖြစ်သွားတာ ကြားက ကွာခြားချက်ပါပဲ။ complexity class တွေကို သိထားခြင်းဟာ profiler တစ်ခု run မလုပ်ခင်ကတည်းက — slug-to-content အတွက် dict lookup တစ်ခုနှင့် lesson record တိုင်းကို linear scan လုပ်ခြင်း — ဘယ် implementation ရွေးချယ်မှုက content ဆက်တိုးလာသည့်တိုင် platform ကို responsive ဖြစ်နေအောင် ထိန်းသိမ်းပေးမလဲဆိုတာကို ကြိုတင်ခန့်မှန်းနိုင်စေပါတယ်။

• Big-O သည် literal runtime second ကို မဟုတ်ဘဲ input size n နှင့်အတူ cost ဘယ်လိုကြီးထွားလဲကို တိုင်းတာသည်
• Constant factor များနှင့် lower-order term များကို လျစ်လျူရှုသည် — O(n) သည် n နှင့် 3n+100 operation နှစ်မျိုးလုံးကို ဖုံးလွှမ်းသည်
• Best ကနေ worst common class များ: O(1), O(log n), O(n), O(n log n), O(n²)

အတူတူ စမ်းရေးကြည့်မယ်

def find_max_linear(numbers):
    # Single pass over all n items -> O(n): cost grows directly with input size
    current_max = numbers[0]
    for num in numbers:
        if num > current_max:
            current_max = num
    return current_max

def lookup_price(catalog, item_name):
    # dict lookup by key -> O(1): cost stays flat no matter how big catalog gets
    return catalog.get(item_name)

numbers = [4, 19, 2, 77, 5, 42]
catalog = {'pen': 500, 'book': 3500, 'bag': 12000}

print('Max (O(n) scan):', find_max_linear(numbers))
print('Price lookup (O(1)):', lookup_price(catalog, 'book'))

element တိုင်းကို တစ်ကြိမ် scan လုပ်ခြင်းမှ 'Max (O(n) scan): 77' နှင့် catalog size ဘယ်လောက်ပဲရှိရှိ dict lookup တစ်ကြိမ်တည်းမှ 'Price lookup (O(1)): 3500' ကို print ထုတ်ပေးသည်။

Wikipedia — Big O notation — Data Structures & Algorithms