နားလည်ထားရမယ့် အချက်
Array တစ်ခု — Python list ရဲ့ အောက်ခြေမှာလည်း — element တွေကို memory contiguous block တစ်ခုထဲမှာ gap မရှိဘဲ တစ်ခုပြီးတစ်ခု ဆက်တိုက် သိမ်းထားပါတယ်။ ဒီ layout ကြောင့်ပဲ `list[i]` ဟာ O(1) operation ဖြစ်တာပါ — runtime က i-th element ကို ရှာနေတာ မဟုတ်ဘဲ `base_address + i * element_size` အဖြစ် memory address အတိအကျကို တိုက်ရိုက်တွက်ချက်ပြီး တည့်တည့်ဝင်သွားတာပါ၊ list ထဲမှာ item 10 ခုရှိရှိ 10 သန်းရှိရှိ arithmetic step တစ်ခုတည်းပါပဲ။ အဲဒီ contiguous layout အတူတူကပဲ front မှာ insert (သို့) delete လုပ်တာကို ကုန်ကျစေတာပါ။ index 0 မှာ element အသစ်တစ်ခု insert လုပ်ရင် ရှိပြီးသား element အားလုံးဟာ နေရာဖန်ဖို့နှင့် contiguous, gap မရှိတဲ့ layout ကို ထိန်းသိမ်းဖို့ right ဘက်ကို slot တစ်ခု physically shift လုပ်ရမှာဖြစ်ပြီး — ရှိပြီးသား element n ခုလုံးကို ထိတဲ့ operation ဖြစ်တဲ့အတွက် O(n) ကုန်ကျပါတယ်။ ပထမဆုံး element ကို delete လုပ်တဲ့အခါလည်း ဆန့်ကျင်ဘက် အတူတူပါပဲ — နောက်က element အားလုံး left ဘက်ကို တစ်ခု shift ဖြစ်သွားပါတယ်။ ဒါဟာ implementation ညံ့ဖျင်းမှု မဟုတ်ဘဲ တကယ့် trade-off တစ်ခုပါ — constant-time random access ပေးတဲ့ property (tight, contiguous packing) အတူတူကပဲ front insertion/deletion တိုင်းမှာ shift လုပ်ခိုင်းနေတာပါ။
လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်
Tutorial Platform က course တစ်ခုစီရဲ့ lesson တွေကို ordered list တစ်ခုအဖြစ် သိမ်းထားတဲ့အတွက် 'chapter 2 ရဲ့ lesson 5' ဆီ တည့်တည့်ခုန်သွားတာဟာ course မှာ lesson ဘယ်နှစ်ခုပဲရှိရှိ O(1) index lookup တစ်ခုပါပဲ။ ဒါပေမယ့် instructor တစ်ဦးက အဲဒီ list ရဲ့ အစဆုံးမှာ lesson အသစ်တစ်ခု — ဥပမာ prerequisite lesson 0 — ထည့်ချင်ရင်တော့ ကျန် lesson အားလုံးရဲ့ position ဟာ တစ်ခုစီ shift ဖြစ်ရမှာဖြစ်ပြီး course တစ်ခုလုံးအပေါ် O(n) operation ဖြစ်သွားပါလိမ့်မယ်။ ဒါက ဒီ course နောက်ပိုင်းမှာ linked list နှင့် အခြား structure တွေက front မှာ insert လုပ်ဖို့ ပိုသက်သာတဲ့ နည်းလမ်း ပေးတဲ့အခါ ပြန်ပြီး ပြန်လည်ဆွေးနွေးမယ့် trade-off အတိအကျပါပဲ။
အတူတူ စမ်းရေးကြည့်မယ်
lessons = ['intro', 'variables', 'loops', 'functions', 'recursion']
# Index access: O(1) -- jumps straight to the memory slot, no matter list size
print('Lesson at index 2:', lessons[2])
# Insert at front: O(n) -- every existing element shifts one slot right to make room
lessons.insert(0, 'prerequisites')
print('After front insert:', lessons)constant-time index lookup မှတစ်ဆင့် 'Lesson at index 2: loops' ကို print ထုတ်ပြီး၊ ပြီးနောက် 'prerequisites' ကို position 0 ထဲ ထည့်ကာ ကျန် lesson အားလုံးကို slot တစ်ခု right ဘက်ကို တွန်းထားတဲ့ list ကို print ထုတ်ပါတယ်။၅ မိနစ် စမ်းကြည့်
timing experiment ငယ်တစ်ခု ရေးပါ — item 100,000 ပါတဲ့ list တစ်ခု ဆောက်ပြီး `list.insert(0, x)` ကို 10,000 ကြိမ် call လုပ်တာနှင့် `list.append(x)` ကို 10,000 ကြိမ် call လုပ်တာကို timing နှိုင်းယှဉ်ပါ။ shifting အကြောင်း သင်လေ့လာခဲ့တာကို သုံးပြီး timing ကွာခြားချက်ကို ရှင်းပြပါ။
သတိလေးတစ်ချက်
'list access က O(1) ပဲ' ဆိုပြီး list operation အားလုံး O(1) လို့ ယူဆမိခြင်း — index access ကတော့ O(1) ဖြစ်ပေမယ့် front (သို့ အဆုံးမှလွဲပြီး ဘယ်နေရာမဆို) မှာ insert/delete လုပ်တာက shift လိုအပ်တဲ့အတွက် O(n) ဖြစ်ပါတယ်။
list တစ်ခုကို အစဉ်လိုက် ဆောက်ဖို့ loop ထဲမှာ `list.insert(0, x)` ကို ထပ်ခါထပ်ခါ call လုပ်ခြင်း — call တစ်ခုစီက O(n) ဖြစ်တယ်ဆိုတာ မသိဘဲ O(n) loop လို့ထင်ရတဲ့အရာကို မတော်တဆ O(n²) algorithm ဖြစ်စေခြင်း။
Python Wiki — Time Complexity — Data Structures & Algorithms