အခန်း ၁ - Algorithms မိတ်ဆက်

Computer Science ဘာသာရပ်ကို လေ့လာလိုက်စားသည့် သူတွေ အတွက် Algorithm ဆိုတာ မသိမဖြစ် လေ့လာရမည့် ဘာသာရပ် တစ်ခု ဖြစ်ပါတယ်။ Developer တစ်ယောက်ရဲ့ အရည်အချင်း၊ သူ ဘယ်လောက်ထိ စဉ်းစားတွေးခေါ်နိုင်ပြီး coding ပြဿနာတွေကို ဖြေရှင်းနိုင်သလဲဆိုတာကို algorithm ပုစ္ဆာများဖြင့် interview များတွင် မကြာခဏ တိုင်းတာလေ့ရှိပါတယ်။

Algorithm ဆိုတာ ဘာလဲ

Algorithm ဆိုတာ ပြဿနာတစ်ခုကို ဖြေရှင်းရန်အတွက် စနစ်တကျ သတ်မှတ်ထားသော အဆင့်ဆင့် လုပ်ဆောင်ရမည့် ညွှန်ကြားချက်များဖြစ်ပါတယ်။ ဥပမာ အားဖြင့် ကျွန်တော်တို့ နေ့စဥ် ဘဝ တွေ မှာ ဟင်းချက်တာ ဖြစ်ဖြစ် ကားမောင်းတာ ဖြစ်ဖြစ် အဆင့်ဆင့် လုပ်ဆောင်ရပါတယ်။ ဥပမာ ဟင်းချက်နည်း တစ်ခု က Algorithm တစ်ခုပါပဲ။

သို့ပေမယ့် computer algorithms တွေဟာ အောက်ပါ ဂုဏ်သတ္တိတွေ ရှိရပါမယ်။

Input : လုပ်ဆောင်ရမည့် အချက်အလက်တွေ ရှိရမည်။
Definiteness : အဆင့်တိုင်းဟာ ရှင်းလင်း တိကျရမည်။
Finiteness: အဆုံးမရှိ ပဲ လုပ်ဆောင်နေတာမျိုး မဟုတ်ပဲ တစ်နေရာမှာ အလုပ်ပြီးမြောက်ပြီး ရပ်တန့် နေရမည်။
Output: အနည်းဆုံး ရလဒ် တစ်ခု ထွက်လာရမည်။
Effectiveness: လက်တွေ့ လုပ်ဆောင်လို့ရသည့် အဆင့်တွေ ဖြစ်ရမည်။

Algorithm ဘာကြောင့်အရေးကြီးလဲ

ယနေ့ခေတ်မှာ Software တွေဟာ ရှုပ်ထွေးလာပါတယ်။ ဥပမာ Facebook မှာ Friend Suggestion, Google Map မှာ route ပြတာ စသည့် စနစ်တွေ ရဲ့ နောက်ကွယ်မှာ အလွန် ရှုပ်ထွေးပြီး အရမ်းကို ကောင်းမွန်သည့် alogrithm တွေ အလုပ်လုပ်နေပါတယ်။ ကျွန်တော်တို့တွေ က နည်းလမ်း မမှန်ပဲ code တွေကို ရေးလိုက်မယ် ဆိုရင် process တစ်ခုက ပုံမှန်ထက် လုပ်ဆောင်ရမည့် အလုပ်ပမာဏ များလာပြီး နှေးသွားတာ ဒါမှမဟုတ် ပိုပြီး powerful ဖြစ်သည့် စက်တွေ လိုအပ်တာမျိုးတွေ ဖြစ်လာနိုင်တယ်။ ဒါကြောင့် algorithm ဟာ အလုပ်လုပ် ရုံတင်မကပဲ အကောင်းဆုံး နဲ့ အမြန်ဆုံး အလုပ်လုပ်ဖို့ အတွက် လေ့လာရခြင်း ဖြစ်ပါတယ်။

Algorithm စွမ်းဆောင်ရည် ကို တိုင်းတာခြင်း (Asymptotic Notations)

Algorithm ဘယ််လောက်ကောင်းသလဲဆိုတာကို စက္ကန့် နဲ့ မတိုင်းတာပါဘူး။ ဘာလို့လဲဆိုတော့ computer တစ်လုံး နဲ့ တစ်လုံးဟာ performance အမြန်နှုန်း မတူညီလို့ပါ။ ဒါကြောင့် အချက်အလက် ပမာဏ ( $n$ ) များလာရင် algorithm က ဘယ်လောက်ထိ အလုပ်လုပ်ရမလဲ ဆိုတာကို သင်္ချာနည်းအရ Asymptotic Notations များ အသုံးပြုပြီး တိုင်းတာပါတယ်။ အဓိကအားဖြင့် အခြေအနေ (၃) မျိုး ခွဲခြားသုံးသပ်ပါတယ်။

Big Omega Notation - $\Omega$ (အကောင်းဆုံး အခြေအနေ / Best Case)

ဒါကို Lower Bound လို့ ခေါ်ပါတယ်။ Algorithm တစ်ခု လုပ်ဆောင်ဖို့အတွက် အနည်းဆုံး ဘယ်လောက် ကြာမလဲ ဆိုတာကို ကိုယ်စားပြုပါတယ်။

ဥပမာ: Linear Search သုံးပြီး Array [5, 2, 9, 1, 7] ထဲမှာ ဂဏန်း 5 ကို ရှာမယ်ဆိုပါစို့။ 5 က ပထမဆုံး နေရာမှာပဲ ရှိနေတဲ့အတွက် ချက်ချင်း တွေ့သွားပါမယ်။ ဒါဟာ Algorithm အကောင်းဆုံး အခြေအနေ (Best Case) ဖြစ်ပြီး Time Complexity ဟာ $\Omega(1)$ ဖြစ်ပါတယ်။

Big O Notation - $O$ (အဆိုးဆုံး အခြေအနေ / Worst Case)

ဒါကို Upper Bound လို့ ခေါ်ပါတယ်။ အယ်ဂိုရီသမ်တစ်ခု လုပ်ဆောင်ဖို့အတွက် အများဆုံး ဘယ်လောက် ကြာမလဲ ဆိုတာကို ကိုယ်စားပြုပါတယ်။

ဥပမာ: အပေါ်က Array ထဲမှာပဲ 7 ကို ရှာမယ်ဆိုရင် နောက်ဆုံးရောက်မှ တွေ့မှာ ဖြစ်သလို၊ 10 ဆိုတဲ့ ဂဏန်းကို ရှာမယ်ဆိုရင်တော့ အကုန်ရှာပြီးမှ လုံးဝ မတွေ့တာမျိုး ဖြစ်နိုင်ပါတယ်။ ဒါဟာ အဆိုးဆုံး အခြေအနေ (Worst Case) ဖြစ်ပြီး Time Complexity ဟာ $O(N)$ ဖြစ်ပါတယ်။
(Software Engineer တွေဟာ အဆိုးဆုံး အခြေအနေကို ကြိုတင်မျှော်မှန်းထားရတဲ့အတွက် လက်တွေ့ လုပ်ငန်းခွင်မှာ Big O ကိုပဲ အများဆုံး အသုံးပြုကြပါတယ်။)

Big Theta Notation - $\Theta$ (Tight Bound)

ဒါကို Tight Bound လို့ ခေါ်ပါတယ်။ အယ်ဂိုရီသမ်တစ်ခုရဲ့ growth rate ကို upper bound နဲ့ lower bound နှစ်ခုလုံးက တူညီစွာ ချုပ်ဆိုနိုင်တဲ့အခါ $\Theta$ notation ကို သုံးပါတယ်။

ဥပမာ: Array [5, 2, 9, 1, 7] ထဲက ဂဏန်း အားလုံးရဲ့ စုစုပေါင်း ပေါင်းလဒ် (Sum) ကို ရှာမယ်ဆိုရင်၊ ကံကောင်းတာ၊ ကံဆိုးတာ မရှိပါဘူး။ ဂဏန်း (၅) လုံးစလုံးကို အမြဲတမ်း ပတ်ပြီး (Loop) ပေါင်းရမှာပါ။ အကောင်းဆုံးကော အဆိုးဆုံးကော $n$ ကြိမ် အလုပ်လုပ်ရတဲ့အတွက် သူ့ရဲ့ Time Complexity ဟာ $\Theta(n)$ ဖြစ်တယ်လို့ အတိအကျ ဆိုနိုင်ပါတယ်။

ဥပမာ

ရန်ကုန် ကနေ မန္တလေး ကို ကားမောင်းသွားတယ် ဆိုပါစို့။ (real world example မဟုတ် ပဲ conceptual example ပါ။)

$\Omega$ (Best Case): လမ်းမှာ လုံးဝကားမပိတ်၊ ရာသီဥတုကကောင်း၊ အမြန်ဆုံး အရှိန်နဲ့ သွားမယ်ဆိုရင် အနည်းဆုံး (၈) နာရီ ကြာမယ်။

$O$ (Worst Case): လမ်းမှာ ကားပိတ်တာ၊ မိုးရွာတာ အဆိုးဆုံးကြုံရင်တောင် အဆိုးဆုံး အခြေအနေအဖြစ် (၁၀) နာရီခန့် ကြာနိုင်တယ်လို့ ယူဆပါစို့။

$\Theta$ (Tight Bound): သာမန်အားဖြင့် အမြဲတမ်း ပုံမှန် မောင်းသွားရင် (၉) နာရီခန့် အတိအကျ ကြာမယ်။

အသုံးများတဲ့ Big O အမျိုးအစားများ

Computer Science မှာ Big O ဟာ လက်တွေ့ အသုံးအများဆုံးပါ။ အမျိုးအစားတွေကတော့

$O(1)$ - Constant Time: Data ဘယ်လောက်များများ ကြာချိန် အတူတူပဲ။ ဥပမာ Array Index တစ်ခု ကို ယူတာ
$O(N)$ - Linear Time : Data များလေလေ အချိန်ကြာလေလေ။ ဥပမာ Array ထဲမှာ အခန်း အစ ကနေ အဆုံး ထိ ရှာဖွေခြင်း
$O(N \log N)$ - Linearithmic Time: O(N) ထက် အနည်းငယ် ပိုကြာသော်လည်း $O(N²)$ ထက် အများကြီး ပိုမြန်တယ်။ ဥပမာ Merge Sort ကဲ့သို့သော Algorithm
$O(N²)$ - Quadratic Time: input size တိုးလာတာနဲ့အမျှ ကြာချိန်က နှစ်ထပ်ကိန်းအချိုးနဲ့ တိုးလာတယ်။ အဆင့်ဆင့် loop ပတ်နေတာမျိုး
$O(\log N)$ - Logarithmic Time: Data များလာပေမယ့် ကြာချိန် အနည်းငယ်ပဲ တိုးလာခြင်း။ မြန်ဆန်သည့် စနစ်လို့ ဆိုနိုင်တယ်။

Big O တွက်ချက်ခြင်း

Big O Notation ကို တွက်ချက်သည့် အခါမှာ အဓိက Golden Rule ၃ ခု ရှိပါတယ်။

အဆင့်ဆင့် တွက်ချက်ခြင်း ဥပမာ

Algorithm ကို အဆင့်ဆင့် ဘယ်လို တွက်ချက်လဲဆိုတာ အောက်ပါ Java Code လေးနဲ့ အရင် လေ့လာကြည့်ရအောင်။

int sum = 0; // 1 
int mul = 1; // 1 
for (int i = 0; i < array.length; i++) { // N ကြိမ် 
    sum = sum + array[i]; // N ကြိမ် 
    mul = mul * array[i]; // N ကြိမ် 
}

အပေါ်က code မှာ အစကိန်းသေ နှစ်ကြောင်းက ၁ ကြိမ်စီ အလုပ်လုပ်တယ်။ Loop က N ကြိမ် ပတ်တယ်။ Loop အထဲက ကုဒ်တွေကလည်း N ကြိမ်စီ အလုပ်လုပ်တယ်။
စုစုပေါင်းလုပ်ဆောင်ချက်ကို 1 + 1 + N + N + N = 2 + 3N ဆိုပြီး အကြမ်းဖျင်း ယူဆလို့ရပါတယ်။

Big O Notation ကို သတ်မှတ်တဲ့အခါ ဒီလို ကိန်းဂဏန်းတွေထဲကနေ အဓိက Golden Rule ၃ ခု ကို အသုံးပြုပါတယ်။

၁။ ကိန်းသေများကို ပယ်ဖျက်ပါ

အပေါ်က တွက်လဒ် 2 + 3N မှာ ကိန်းသေ (Constants) တွေဖြစ်တဲ့ အပေါင်း 2 နဲ့ အမြှောက် 3 ကို ပယ်ဖျက်ပါတယ်။ ဒါကြောင့် အကျဉ်းချုံးလိုက်ရင် $O(N)$ လို့ပဲ သတ်မှတ်ပါတယ်။ Algorithm တစ်ခုက $O(2N)$ သို့မဟုတ် $O(N+100)$ အဆင့်တွေ ယူတယ်ဆိုရင်လည်း ကိန်းသေ တွေကို ပယ်ဖျက်ပြီး $O(N)$ လို့ပဲ သတ်မှတ်ပါတယ်။ အချက်အလက် ဘယ်လောက် ပွားလာလဲ ဆိုသည့် အချိုးအဆ ကို ပဲ အဓိက ထားလို့ပါ။

၂။ အဓိက မကျသည့် ကိန်းများကို ပယ်ဖျက်ပါ

Algorithm ရဲ့ ကြာချိန်က တွက်လိုက်လို့ $O(N^2 + N)$ ဖြစ်နေခဲ့လျှင် $N^2$ က $N$ ထက် အများကြီး ပိုမြန်မြန် ကြီးထွားလာနိုင်သည့် အတွက် အရေးမပါတဲ့ $N$ ကို ပယ်ဖျက်ပြီး $O(N^2)$ လို့ ပဲ ယူပါတယ်။

public void printNumbers(int[] array) {
    for (int i = 0; i < array.length; i++) { // O(N)
        System.out.println(array[i]);
    }
    
    for (int i = 0; i < array.length; i++) { // O(N^2)
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + array[j]);
        }
    }
}

အပေါ်က ဥပမာမှာ ပထမ Loop က $O(N)$ ကြာပြီး၊ ဒုတိယ Loop အထပ်က $O(N^2)$ ကြာပါတယ်။ စုစုပေါင်း Time Complexity က $O(N^2 + N)$ ဖြစ်ပေမယ့်၊ $N$ ဟာ တဖြည်းဖြည်း အရေးမပါတော့တဲ့အတွက် ပယ်ဖျက်လိုက်ပြီး $O(N^2)$ လို့ပဲ သတ်မှတ်ပါတယ်။

၃။ ပေါင်းခြင်း နှင့် မြှောက်ခြင်း

အဆင့် $A$ လုပ်ပြီးမှ အဆင့် $B$ ကို ဆက်လုပ်တယ်။ အဲဒီလို case ဆိုရင် ပေါင်းပါတယ်။ $O(A+B)$

for (int i = 0; i < arrayA.length; i++) { // O(A)
    System.out.println(arrayA[i]);
}
for (int j = 0; j < arrayB.length; j++) { // O(B)
    System.out.println(arrayB[j]);
}
// Time Complexity: O(A + B)

အဆင့် $A$ တစ်ခါလုပ်တိုင်း အဆင့် $B$ ကို ထပ်ခါ ထပ်ခါ လုပ်ရတယ်။ ဥပမာ Nested Loop လိုမျိုး ဆိုရင် မြှောက်ပါတယ်။ $O(A \times B)$

for (int i = 0; i < arrayA.length; i++) { // O(A)
    for (int j = 0; j < arrayB.length; j++) { // O(B)
        System.out.println(arrayA[i] + arrayB[j]);
    }
}
// Time Complexity: O(A * B)

Time Complexity

Time Complexity ဆိုတာ အချက်အလက် ပမာဏ $N$ အပေါ်မှာ မူတည်ပြီး Algorithm အလုပ်လုပ်ရသည့် အကြိမ်အရေ အတွက် ဘယ်လောက် များလဲဆိုတာ တိုင်းတာခြင်း ဖြစ်ပါတယ်။

$O(1)$ Constant Time

အချက်အလက် ဘယ်လောက်ပဲများများ အလုပ်လုပ်ရသည့် အချိန် အတူတူပါပဲ။

public void printFirstElement(int[] array) {

    // Array ထဲမှာ ဂဏန်း ၁၀ လုံးပဲရှိရှိ၊ သန်း ၁၀ဝ ပဲရှိရှိ
    // ပထမဆုံး ဂဏန်းကို ယူဖို့ ကြာချိန်က အတူတူပါပဲ။
    System.out.println(array[0]); // O(1)
}

$O(N)$ Linear Time

အချက်အလက်ပမာဏ များလာတာနဲ့အမျှ ကြာချိန်ကလည်း တိုက်ရိုက် အချိုးကျ များလာပါတယ်။ Array က ၁၀ ဆ ကြီးလာရင် ကြာချိန် ၁၀ ဆ ပိုကြာပါမယ်။

public void printAllElements(int[] array) {
    // Loop က Array ရဲ့ အရွယ်အစား (N) အကြိမ် အရေအတွက်အတိုင်း အလုပ်လုပ်ပါတယ်။
    for (int i = 0; i < array.length; i++) { // O(N)
        System.out.println(array[i]);
    }
}

$O(N²)$ Quadratic Time

အချက်အလက် ပမာဏ များလာသည်နှင့် အမျှ ကြာချိန် က နှစ်ထပ်ကိန်း (Square) အချိုးနဲ့ များလာပါတယ်။ များသော အားဖြင့် Loop နှစ်ထပ် (Nested Loop) တွေ မှာ တွေ့ရပါတယ်။

public void printAllPairs(int[] array) {
    // အပြင် Loop က N ကြိမ် အလုပ်လုပ်တယ်
    for (int i = 0; i < array.length; i++) {
        // အတွင်း Loop ကလည်း အပြင် Loop တစ်ခါပတ်တိုင်း N ကြိမ် ထပ်လုပ်တယ်
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}
// Time complexity: O(N * N) = O(N^2)

$O(\log N)$ Logarithmic Time

အလွန်မြန်ဆန်သည့် Algorithm လို့ ဆိုလို့ရပါတယ်။ အချက်အလက်တွေ များလာပေမယ့် ကြာချိန် က အနည်းငယ်ပဲ တိုးလာပါတယ်။ အဆင့် တစ်ဆင့် လုပ်တိုင်း ကျန်နေသည့် အချက်အလက် တစ်ဝက်ကို ပယ်ဖျက်သွားနိုင်သည့် လုပ်ငန်းစဥ်တွေ ဖြစ်ပါတယ်။ ဥပမာ Binary Search လိုမျိုးပေါ့။

Algorithm မှာ Log ဆိုတာ

ပုံမှန် သင်္ချာမှာ log ဆိုရင် Base 10 သို့မဟုတ် Base e ကို ယူဆပါတယ်။ Computer Science မှာတော့ $\log N$ လို့ ရေးထားခဲ့ရင် Base 2 ( $\log_2 N$ )ဖြစ်ပါတယ်။

$\log_2 N$ ဆိုတာ ဘာလဲ ?**

log₂ N ဆိုတာ 1 ရောက်အောင် 2 နဲ့ ဘယ်နှကြိမ်စားနိုင်လဲဆိုတာကို ဖော်ပြတာပါ။

N = 8 ဆိုပါစို့ ။ 8 ကို တစ်ဝက်စီ ပိုင်း ခဲ့ရင် ၃ ခါ ပိုင်းရပါတယ်။ 8 → 4 → 2 → 1 ။ တနည်းပြောရင် 8 = $2³$ ပါ။ အဲဒီ အဓိပ္ပာယ်က $log_2 (8) = 3$ နဲ့ အတူတူပါပဲ။

ဥပမာ Array ထဲမှာ အခန်း အရေအတွက် 1024 ရှိတယ် ဆိုပါစို့။ N = 1024 ပါ။ Algorithm ရဲ့ Big O က $O(log_2 N)$ ဆိုပါစို့။

$log_2 (1024) = 10$ ရပါတယ်။ ဒါကြောင့် ဒီ alogrithm က အရမ်းမြန်တယ်။ 1024 အခန်းတောင် 10 ကြိမ်ပဲ အလုပ်လုပ်ရပါတယ်။ Time Complexity ကောင်းတယ်လို့ ဆိုရပါမယ်။

public int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (sortedArray[mid] == target) {
            return mid;
        }

        // အဆင့်တစ်ဆင့်တိုင်းမှာ ရှာရမယ့်အပိုင်းကို တစ်ဝက်စီ လျှော့ချပစ်ပါတယ်။
        if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

// Time complexity: O(log N)

$O(N \log N)$ Linearithmic Time

$O(N)$ ထက် အနည်းငယ် ပိုကြာသော်လည်း $O(N^2)$ ထက် အများကြီး ပိုမြန်ပါတယ်။ အချက်အလက်တွေကို တစ်ဝက်စီ ပိုင်းခြားပြီးမှ ပြန်လည်ပေါင်းစပ်တဲ့ (Divide and Conquer) အယ်ဂိုရီသမ်တွေမှာ အများဆုံး တွေ့ရပါတယ်။ အကောင်းဆုံး Sorting Algorithm (ဥပမာ - Merge Sort, Quick Sort) ရဲ့ Time Complexity ဖြစ်ပါတယ်။

// အသေးစိတ်ကို နောက်ပိုင်း လေ့လာရပါမည

public void sortArray(int[] array) {
    java.util.Arrays.sort(array); 
}

// Time complexity: O(N log N)

Sorting algorithm အများစု၏ average time complexity သည် O(N log N) ဖြစ်သည်။

$O(2^N)$ Exponential Time

အချက်အလက် တစ်ခုတိုးလာတိုင်း ကြာချိန်က ၂ ဆစီ ပွားသွားပါတယ်။ များသောအားဖြင့် Branch တွေ အများကြီးခွဲထွက်သွားတဲ့ Recursive အယ်ဂိုရီသမ်တွေမှာ တွေ့ရပါတယ်။

public int fibonacci(int n) {
    if (n <= 1) return n;
    // Function တစ်ခါခေါ်တိုင်း နောက်ထပ် Function ၂ ခုကို ပြန်ခွဲထွက်သွားပါတယ်
    return fibonacci(n - 1) + fibonacci(n - 2); 
}

// Time complexity: O(2^N)

Space Complexity (မှတ်ဉာဏ် အသုံးပြုမှု)

Space Complexity ဆိုတာ Algorithm မှာ အလုပ်လုပ်ဖို့အတွက် Memory ဘယ်လောက် လိုအပ်လဲ ဆိုတာကို တိုင်းတာတာပါ။ Data (Input) ယူထားတဲ့ နေရာကိုတော့ ထည့်မတွက်ပါဘူး။ Data အသစ်ဖန်တီးတာ၊ Array အသစ် ဆောက်တာတွေကိုပဲ ထည့်တွက်ပါတယ်။

$O(1)$ Constant Space

Input Data ဘယ်လောက်များများ၊ memory အသစ်မလိုပါဘူး။

public int sumArray(int[] array) {
    int sum = 0; // Integer variable တစ်ခုစာပဲ နေရာယူပါတယ်။ (O(1) space)
    for (int i = 0; i < array.length; i++) {
        sum += array[i]; 
    }
    return sum;
}

// Space Complexity: O(1)

$O(N)$ Linear Space

Input Data ပမာဏနဲ့ အချိုးကျပြီး Memory လိုအပ်ပါတယ်။

public int[] copyArray(int[] array) {

    // မူလ Array ရဲ့ အရွယ်အစား N နဲ့တူညီတဲ့ Array အသစ်တစ်ခုကို တည်ဆောက်ပါတယ်။

    int[] newArray = new int[array.length]; // O(N) space

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

    return newArray;

}

// Space Complexity: O(N)

$O(N^2)$ - Quadratic Space

Input Data ကို မူတည်ပြီး 2D Array (သို့) Matrix တွေ တည်ဆောက်တဲ့အခါ တွေ့ရပါတယ်။

public int[][] createMatrix(int n) {

    // N x N အရွယ်အစားရှိတဲ့ Matrix အသစ် တည်ဆောက်တာ ဖြစ်ပါတယ်။

    int[][] matrix = new int[n][n]; // O(N * N) space

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = i + j;
        }
    }

    return matrix;

}

// Space Complexity: O(N^2)

Time Complexity နှင့် Space Complexity တို့၏ Trade-Off

လက်တွေ့မှာ အကောင်းဆုံး နဲ့ memory အနည်းဆုံး နှစ်ခု လုံး ရဖို့ မလွယ်ကူပါဘူး။ တစ်ခုကို လိုချင်လျှင် တစ်ခုကို အလျော့ပေးရပါမယ်။ Trade Off လုပ်ရတာပေါ့။

Time Complexity ကောင်းချင်လျှင် Space Complexity အားနည်းပါတယ်။ ဥပမာ Caching လိုမျိုး ပြန်တွက်စရာ မလိုပဲ သိမ်းထားသည့် ကိစ္စတွေမှာ Time Complexity ကောင်းပေမယ့် Space Complexity မကောင်းပါဘူး။
Space Complexity ကောင်းချင်လျှင် Time Complexity အားနည်းပါတယ်။ တွက်ချက်မှု တွေကို ကြိုတင်သိမ်းထားမှု မရှိပဲ လိုမှ တွက်သလိုမျိုးပေါ့။

ဥပမာ - Array တစ်ခုတည်းမှာ နံပါတ်တွေ ထပ်နေတာ (Duplicates) ရှိမရှိ စစ်ဆေးခြင်း

နည်းလမ်း ၁။ Nested Loops သုံးခြင်း (ကြာချိန် နှေးသွားမည်၊ မှတ်ဉာဏ် သက်သာမည်)

public boolean hasDuplicatesSlow(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) return true;
        }
    }

    return false;

}

// Time: O(N^2) - ဂဏန်းတစ်လုံးကို ကျန်တဲ့ဂဏန်းတိုင်းနဲ့ လိုက်စစ်ရလို့ ကြာပါတယ်။
// Space: O(1) - Data အသစ်/Array အသစ် ထပ်မဆောက်လို့ မှတ်ဉာဏ် လုံးဝသက်သာပါတယ်။

နည်းလမ်း ၂။ HashSet သုံးခြင်း (နောက်ပိုင်း အခန်းတွေမှာ memoization အကြောင်း တွေ့ရပါမည်)

public boolean hasDuplicatesFast(int[] array) {

    HashSet<Integer> seen = new HashSet<>(); // Memory အသစ် ယူလိုက်ပါပြီ!
    for (int num : array) {
        if (seen.contains(num)) return true; // ရှာရတာ O(1) ဖြစ်လို့ မြန်ပါတယ်
        seen.add(num);
    }
    return false;
}

// Time: O(N) - Array ကို တစ်ခေါက်ပဲ ပတ်စရာလိုတဲ့အတွက် မြန်ပါတယ်။
// Space: O(N) - ဂဏန်းတွေကို HashSet ထဲအသစ်ပြန်ထည့်ရလို့ Memory (N) စာ ပိုယူသွားပါတယ်။

အခု ဆိုရင် အနည်းငယ် သဘောပေါက်ပြီလို့ ထင်ပါမယ်။ နောက်ပိုင်း အခန်းတွေ မှာ algorithm တိုင်း ကို Time Complexity နဲ့ Space Complexity ကို ဖော်ပြပေးသွားပါမယ်။ တချို့ sorting တွေမှာ တော့ အသေးစိတ် ပြန်လည် ရှင်းပြပါမယ်။ ထို့မှသာ နားလည် လွယ်ပါလိမ့်မယ်။

အခန်း ၁ - Algorithms မိတ်ဆက်

Algorithm ဆိုတာ ဘာလဲ

Algorithm ဘာကြောင့်အရေးကြီးလဲ

Algorithm စွမ်းဆောင်ရည် ကို တိုင်းတာခြင်း (Asymptotic Notations)

Big Omega Notation - Ω\OmegaΩ (အကောင်းဆုံး အခြေအနေ / Best Case)

Big O Notation - OOO (အဆိုးဆုံး အခြေအနေ / Worst Case)

Big Theta Notation - Θ\ThetaΘ (Tight Bound)

အသုံးများတဲ့ Big O အမျိုးအစားများ

Big O တွက်ချက်ခြင်း

Time Complexity

O(1)O(1)O(1) Constant Time

O(N)O(N)O(N) Linear Time

O(N2)O(N²)O(N2) Quadratic Time

O(log⁡N)O(\log N)O(logN) Logarithmic Time

O(Nlog⁡N)O(N \log N)O(NlogN) Linearithmic Time

O(2N)O(2^N)O(2N) Exponential Time