Big O အကြောင်းရေးတော့ O(log n) အကြောင်းပါတစ်ခါတည်းရှင်းပြမလို့ဘဲ။ ဒါပေမယ့် Logarithms ဆိုတာဘာလည်းရှင်းပြရဦးမယ်ဆိုပြီး နောက်ထပ် Post တစ်ခုလုပ်ဖို့ဆုံးဖြတ်လိုက်တာ။ ဒီ Post မှာ Logarithms ကို ရှင်းပြရင်းနှင့် O(log n) ပါတစ်ခါတည်းရှင်းပြပါ့မယ်။ ကျောင်းတုန်းကတော့ Logarithm ကိုသင်ခဲ့ဖူးတယ်။ ကျွန်တော်တော့မေ့ကုန်လို့ Khan Academy ကပြန်ကြည့်ရတယ်။

ပထမဆုံး Logarithms ဆိုတာဘာလဲကအရင်စရှင်းကြရအောင်…

အထက်ဖော်ပြပါပုံရဲ့ ပထမ line မှာဆိုရင် 2 ^ 4 (2 power 4) က (2 x 2 x 2 x 2) 2 ကိုလေးခါမြှောက်တာနှင့်တူတယ်။ ဒုတိယ line မှာဆိုရင် 2 ^ x = 16 ဖြစ်တယ်ဆိုရင် ဒီနေရာမှာ x ရဲ့တန်ဖိုးက 4။ အဲ့ဒါကို logarithm နှင့်တတိယ line မှာ log base 2 of 16 က x နှင့်တူတယ်။ ဆိုလိုချင်တာက Log base 2 of 16 = 4. ဒီနေရာမှာ 4 ဆိုတာက 2 ကိုမြှောက်ရတဲ့ exponents. 16 ရဖို့ 2 power ဘယ်လောက်တင်ရမလဲဆိုတဲ့ Value ။

ပိုလွယ်အောင်လို့ နောက်ထပ်ဥပမာတစ်ခုနှင့်ထက်ရှင်းပြလိုက်မယ်။ log base 5 of 125 ရဲ့ထပ်ကိန်း (exponents) ကိုရှာပါဆိုရင် 5 ရဲ့ထပ်ကိန်း 3 က 125 ဆိုတော့ အဖြေက 3။

= log base 5 of 125 = x
= 5^x = 125
= x = 3

--------------------------

= log base 10 of 1000 = x
= 10 ^ x = 1000
= x = 2

အိုကေ… ကျွန်တော်တို့ဒီလောက်ဆို Logarithms ဆိုတာကိုနားလည်သွားလောက်ပြီ။ ကျွန်တော် Big O အကြောင်းရေးခဲ့တုန်းက O(log(n)) အကြောင်းမပြောခဲ့ဘူး။ အခု Logarithm အကြောင်းပြောရင်းနှင့် O(log n) ဘယ်လိုတွက်မလဲဆိုတာပါရှင်းပြသွားပါ့မယ်။

O(log n) ဘယ်လိုတွက်မလဲ…

ကျွန်တော် Big O အကြောင်းပြောတုန်းက O(n) တို့ O(1) တို့ဆိုတာ ရိုးရိုးရှင်းရှင်းဘဲ။ တော်တော်လေးလည်းနားလည်လွယ်တယ်။ O(log n) လည်းရောက်ရောနည်းနည်းတိုင်ပတ်တာဘဲ။

O(log n) ကိုတွက်မယ်ဆိုရင် O(log n) သုံးတဲ့ Algorithm တစ်ခုဖြစ်တဲ့ Binary Search Tree (BST) နှင့်နည်းနည်းရှင်းပြမှပိုမြင်မယ်ထင်တယ်။ BST ကိုတော့သိကြမယ်ထင်ပါတယ်။ ကျွန်တော်တို့ BST ကိုသုံးပြီးတော့ sorted array ရှာတာကိုပြောပြရင်းနှင့် O(log n) ကိုတွက်သွားမှာဖြစ်ပါတယ်။

တကယ်လို့ Binary Search Tree ကိုမသိသေးဘူးဆိုရင် Learn Data Structure in Burmese ဆိုတဲ့ article ရှိပါတယ်။ အဲ့ကောင်ကိုအရင်သွားဖတ်ကြည့်ပါ။

ကျွန်တော်တို့မှာ 16 values ရှိတဲ့ sorted array တစ်ခုရှိတယ်ထားပါစို့။

Values => 1 3 5 8 12 13 15 16 18 20 22 30 40 50 55 67
Indexs => 0 1 2 3  4  5  6  7  8  9 10 11 12 13 14 15

အားလုံးသိတဲ့အတိုင်းဘဲ BST က best-case မှာဆို O(1) worst-case မှာဆို O(log n) ဒီနေရာမှာ worst-case ဖြစ်တဲ့ 13 ကိုရှာမယ်ထားပါတော့။

အဲ့တော့ BST အလုပ်လုပ်တဲ့ပုံစံအတိုင်းတစ်ဝက် 1/2 of 16 ဝက်လိုက်မယ်။ ပြီးတော့လိုချင်တဲ့ value ကဘယ်ဘက်မှာလားညာဘက်မှာလားကြည့်လိုက်မယ်။ ကျွန်တော်တို့ case မှာဆို ဘယ်ဘက်မှာရှိတယ်။ Index 0 ကနေ 7 ထိ။ အဲ့ကနေတစ်ဆင်ထက်ဝက်ထက်ဝက်တယ် 1/2 of 8။ ကနေထက်ဝက်တယ် 1/2 of 4။ အဲ့ကနေမှ 1/2 of 2။ နောက်ဆုံးကျွန်တော်တို့ရှာချင်တဲ့ 13 ကိုရှာလို့တွေ့သွားတယ်။

မရှာရသေးခင် Values များ

1 3 5 8 12 13 15 16 18 20 22 30 40 50 55 67

ပထမ - 1/2 of 16 = 8
Values => 1 3 5 8 12 13 15 16

ဒုတိယ - 1/2 of 8 = 4
12 13 15 16

တတိယ - 1/2 of 4 = 2
12 13

စတုတ္တ - 1/2 of 2 = 1
13

အဲ့တော့ကျွန်တော်တို့ရှာချင်တဲ့ 13 ကိုတွေ့ဖို့အတွက် array value 16 ကို 4 ခါဝက်လိုက်ရတယ်။ အဲ့ကောင်ကိုကျွန်တော်တို့ 16*(1/2)^4 = 1 လို့ပြောလို့ရတယ်။ ဒီနေရာမှာ 16 ဆိုတာက lengths. ကျွန်တော်တို့အရင် Algorithm တွေမှာတုန်းကလိုဘဲ n ဆိုပြီးသတ်မှတ်မယ်ဆိုရင် n * (1/2) ^ k = 1 ပေါ့။ သူ့ကို simplify လုပ်မယ်ဆိုရင်

n * (1/2)^k = 1

n * 1/2^k = 1

n/2^k = 1

2^k * n/2^k = 1 * 2^k

n = 2 ^ k is equal to log base2 of n = k

ကျွန်တော်တို့ log base 2 of n = k ကိုရှင်းရင် k = 4 ရမယ်။ ကျွန်တော်တို့ case မှာဆို 4 ခါရှာလိုက်ရတယ်။ ဒီလောက်ဆိုရင် Logarithms ဆိုတာဘာလဲနှင့် O(log n) ဘယ်လိုတွက်ရမလဲသိလောက်ပြီထင်ပါတယ်။

ကြမ်းကိုများ
– https://www.youtube.com/watch?v=4UNkQcBrLaQ&list=PLmdFyQYShrjcWl13fndjdWRBTF0C-tHG3
– Binary Search O = Log N