Exercise: Time Complexity ခွဲခြမ်းစိတ်ဖြာခြင်း

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

Code ကို ဖတ်ပြီး complexity ခန့်မှန်းတာဟာ ခန့်မှန်းချက်မဟုတ်ဘဲ၊ ထပ်ခါထပ်ခါ သုံးလို့ရတဲ့ method တစ်ခုပါ။ ပထမဆုံး loop nesting ကို ရေတွက်ပါ — item n ခုကို တစ်ခါပဲ ဖြတ်တဲ့ single loop ဆိုရင် O(n)၊ n နဲ့ scale ဖြစ်တဲ့ loop နှစ်ခု nested ဖြစ်နေရင် O(n²) ဖြစ်ပြီး multiply လုပ်ရပါတယ် — ဒါပေမယ့် inner loop ရဲ့ bound က n ပေါ်မူတည်မှသာ ဒီအတိုင်း ဖြစ်ပါမယ်။ Loop တစ်ခုက fixed number (26 ဒါမှမဟုတ် 10) ပဲ အမြဲ run ရင် n ပေါ်မူတည်တဲ့ variable မဟုတ်ဘဲ constant factor တစ်ခုသာ ဖြစ်တာကြောင့် drop လုပ်ရပါမယ်။ နောက်တစ်ဆင့်မှာ halving pattern ကို ရှာပါ — problem ရဲ့ ကျန်ရှိအစိတ်အပိုင်းကို step တိုင်းမှာ constant factor တစ်ခုနဲ့ ခွဲပစ်တဲ့ loop သို့မဟုတ် recursion (binary search, balanced tree traversal) ဟာ O(log n) ဖြစ်ပါတယ်၊ ဘာလို့လဲဆိုတော့ n ကို 1 အထိ shrink လုပ်ဖို့ လိုတဲ့ step အရေအတွက်ဟာ log₂n ဖြစ်လို့ပါ။ ပြီးရင် operation တစ်ခုချင်းစီကို classify လုပ်ပါ — dict/set membership နဲ့ lookup ဟာ hashing ကြောင့် average အားဖြင့် O(1)၊ arithmetic နဲ့ comparison လည်း O(1) ဖြစ်ပေမယ့် list.insert(0, x)၊ list.pop(0)၊ list ပေါ်မှာ `in` သုံးတဲ့ linear search၊ loop ထဲမှာ `+=` နဲ့ string ကို ထပ်ခါထပ်ခါ ဆက်ခြင်းတို့ဟာ structure တစ်ခုလုံးကို shift ဒါမှမဟုတ် rescan ပြန်လုပ်ရလို့ O(n) စီ ဖြစ်ပါတယ်။ နောက်ဆုံးမှာ အစိတ်အပိုင်းတွေကို မှန်ကန်စွာ ပေါင်းစပ်ပါ — sequentially run ဖြစ်တဲ့ statement တွေကတော့ cost ကို *ပေါင်း* ရမယ် (ပြီးရင် term အကြီးဆုံးအထိ ချုံ့ပါ)၊ loop ထဲမှာ nested ဖြစ်တဲ့ statement တွေကတော့ *မြှောက်* ရပါမယ်။ Constant တွေနဲ့ lower-order term တွေကို အမြဲ drop လုပ်ပါ — n ကြီးလာတဲ့အခါ dominant term ကသာ အရေးကြီးပါတယ်။

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

Tutorial Platform ရဲ့ engineer တွေက "related lessons" feature ကို review လုပ်နေတယ်လို့ မြင်ကြည့်ပါ။ Function တစ်ခုက lesson n ခုစီကို ကျန်တဲ့ lesson အားလုံးနဲ့ နှိုင်းယှဉ်ပြီး similarity ရှာနေတယ်ဆိုရင်၊ ဒါဟာ O(n²) ဖြစ်နေတာကို code ကို ဖတ်ပြီး ချက်ချင်း ဖော်ထုတ်နိုင်ရမယ်။ Lesson အရေအတွက် ၅၀ ရှိရင် ok ပေမယ့် ၅၀,၀၀၀ ရှိရင် production မှာ timeout ဖြစ်နိုင်တယ်။ Time complexity ကို ဖတ်တတ်ခြင်းက scale မတိုးခင် bottleneck တွေကို audit အနေနဲ့ ကြိုတွေ့ဖို့ engineer တွေအတွက် အခြေခံ tool တစ်ခု ဖြစ်ပါတယ်။

• Loop nesting ကို ရေတွက်ပါ — nested loop က n ပေါ်မူတည်မှသာ multiply လုပ်ပါ၊ fixed-count loop ကို constant အနေနဲ့ drop လုပ်ပါ။
• Halving pattern (binary search စသည်) ကို O(log n) အနေနဲ့ မှတ်ထားပါ၊ dict/set lookup ကို O(1)၊ list.insert(0,x) နဲ့ linear search ကို O(n) အနေနဲ့ မှတ်ထားပါ။
• Sequential statement တွေကို ပေါင်းပြီး dominant term ချုံ့ပါ၊ nested statement တွေကို မြှောက်ပါ။

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

# Snippet A
def sum_all(items):
    total = 0
    for x in items:          # single loop over n items
        total += x
    return total

# Snippet B
def has_duplicate_pair(items):
    n = len(items)
    for i in range(n):       # outer loop over n
        for j in range(n):   # inner loop also over n
            if i != j and items[i] == items[j]:
                return True
    return False

# Snippet C
def count_seen(items, seen_set):
    count = 0
    for x in items:          # loop over n
        if x in seen_set:    # set membership is O(1) average
            count += 1
    return count

# Snippet D
def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:           # search space halves each iteration
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

မှန်ကန်တဲ့ အဖြေက Snippet A က O(n)၊ Snippet B က O(n²)၊ Snippet C က O(n) (set lookup က O(1) ဖြစ်လို့ loop တစ်ခုတည်းက dominate လုပ်တယ်)၊ Snippet D က O(log n) ဖြစ်ကြောင်း အတည်ပြုနိုင်ပါမယ်။

Python Wiki — Time Complexity — Data Structures & Algorithms