သင်္ကေတ အဝ် ဇၞော်
သင်္ကေတ အဝ် ဇၞော် (အၚ်္ဂလိက်: Big O notation) ဟီုမ္ဂးဂှ် ဒှ် သင်္ကေတ သင်္ချာ မွဲ မစကာ သွက်ဂွံ ဗၟံက်ထ္ၜး ပရူ အကာဲအရာ ပရေင်ဇၞော်မောဝ် ဟွံသေင်မ္ဂး အကာဲအရာ လက္ကရဴအိုတ် သွက် ဖန်ယှေန် (Limiting behavior of a function) ကာလ အရာမလုပ် (Argument/Input) တအ် ပြံင်လှာဲ တိုန်အာ ဇၞော်ဇၞော် ဟွံသေင်မ္ဂး စိုပ်အာ ဌာန် ဟွံမဲအပိုတ်အခြာ (Infinity) ရ။ ပ္ဍဲကဵု သိပ္ပံ ကောန်ပျူတာ (Computer science) မ္ဂး၊ သင်္ကေတဏအ်ဝွံ ဒှ် သဇိုင် အဓိကအိုတ် သွက်ဂွံ သ္ၚေဝ်ဂၠေပ် ကေုာံ ၜတ်ကၞာတ် အစောံသတ္တိ အလ်ဂဝ်ရဳထမ် (Algorithm) ဂမၠိုင် ဒဒှ်ရ ဍေဟ်တအ် ကေတ် အခိင် ဗလိုင်လဵု (Time complexity) ကေုာံ စကာ ဒၞာဲ သမ္တီ တင်ဂၞင် ဗလိုင်လဵု (Space complexity) ရ။[၁]
သင်္ကေတ အဝ် ဇၞော် ဝွံ ပါလုပ် ပ္ဍဲ ဂကောံ သင်္ကေတ မကော်စ သင်္ကေတ လာန်ဒေါဝ် (Landau's symbols) တုဲ ဍေဟ် ဟွံရိုဟ်လၟိဟ် စွံအာရီု လတူ လၟိဟ်တန် (Constants) ကေုာံ အရာမနွံ အစောံသတ္တိ ဍောတ်တ် တအ်ရ။ ဍေဟ် အာရီုစွံ ဆ လတူ အရာ မဇၞော်မောဝ် ပြဟ်အိုတ် (Dominant term) သၟးရ။ လိက်ပရေင် ဏအ်ဝွံ သ္ၚေဝ်ဂၠေပ် လဝ် ပရူ သင်္ကေတ အဝ် ဇၞော် နကဵု လညာတ် သင်္ချာ၊ သိပ္ပံကောန်ပျူတာ၊ ဝင် ကေုာံ ပရေင်စကာ ဍေဟ် ဗွဲမလှဲလး ရ။
၁။ နိဒါန် ကေုာံ ပွံက်အဓိပ္ပါယ် (Introduction and Definition)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]သင်္ကေတ အဝ် ဇၞော် ဝွံ စကာ လဝ် မလိက် အင်္ဂလိက် "O" မဒှ် ပရေင်ဖ္ဍန် နူကဵု ဝေါဟာရ "Order of growth" (လၟေင် ပရေင်ဇၞော်မောဝ်) ရ။ ကာလ ပိုယ် သ္ၚေဝ်ဂၠေပ် အလ်ဂဝ်ရဳထမ် မွဲမ္ဂး၊ ညးမချူ ပရဝ်ဂရာမ် (Programmers) တအ် မိက်ဂွံ တီ ဒဒှ်ရ ယဝ်ရ တင်ဂၞင် မလုပ် (Input size) $n$ ဂှ် ဇၞော် တိုန် အာ မ္ဂး၊ အခိင် မဒးစကာ သွက်ဂွံ တွက်ဂွံ သွဟ် ဂှ် ဇၞော် တိုန် အာ ဗီုလဵု ရော ဂှ်ရ။
ဥပမာ - ယဝ်ရ အလ်ဂဝ်ရဳထမ် မွဲ ကေတ် အခိင် တွက်ဂၞန် $T(n) = 4n^2 + 3n + 10$ စက္က သွက် တင်ဂၞင် လၟိဟ် $n$ မ္ဂး၊ ကာလ $n$ ဇၞော် ဗွဲမလောန် (ဥပမာ - $n = 1,000,000$) မ္ဂး၊ သွဟ် မကၠုင် နူ $n^2$ ဂှ် ဇၞော်လောန် တုဲ သွဟ် မကၠုင် နူ $3n$ ကဵု $10$ ဂှ် အောန် လောန် တုဲ ဟွံဒး စွံ အာရီု ရ။ သာ်ဂှ် ဟွံသေင် လၟိဟ်တန် $4$ ဂှ်လေဝ် ဟွံဒှ် အရာ အဓိက သွက် ပရေင်ၜတ်ကၞာတ် လညာတ် သဳအိုရဳ ရ။ ဟိုတ်ဂှ်ရ ပ္ဍဲကဵု သင်္ကေတ အဝ် ဇၞော် မ္ဂး ပိုယ် စၟတ်သမ္တီ ဍေဟ် နဒဒှ် $O(n^2)$ ရ။
သင်္ကေတ ဏအ်ဝွံ ကဵု အခေါင် ကု တၠပညာ ကောန်ပျူတာ တအ် သွက်ဂွံ ၜတ်ကၞာတ် ကေုာံ ရုဲစှ် အလ်ဂဝ်ရဳထမ် မကိတ်ညဳ အိုတ် သက်မဒး စွံအာရီု လတူ အစောံသတ္တိ ဟာတ်ဝလ် (Hardware speed) ဟွံသေင်မ္ဂး အရေဝ်ဘာသာ ပရဝ်ဂရာမ် (Programming language) ရ။
၂။ ဝင် ကေုာံ ပရေင်ဇၞော်မောဝ် (History and Development)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]သင်္ကေတ အဝ် ဇၞော် ဝွံ ကတဵုဒှ် ကၠုင် လဝ် ပ္ဍဲ လပါ်ကၞောတ် ဗွဝ်ကၠံ ၁၉ တေအ် ရ။ ပ္ဍဲ သၞာံ ၁၈၉၄ ဂှ် တၠပညာ သင်္ချာ ဂျာမနဳ အစာ ပေါလ် ဗာတ်မန် (Paul Bachmann) စကာ လဝ် သင်္ကေတ "O" ဏအ် ကိုပ်ကၠာ အိုတ် ပ္ဍဲကဵု ပြကိုဟ် ညးတေအ် မနွံ ယၟု Analytische Zahlentheorie (Analytical Number Theory) ရ။[၂]
လက္ကရဴ ဂှ် တၠပညာ သင်္ချာ ဂျာမနဳ မွဲတၠ ပၠန် မနွံ ယၟု အက်ဒမန် လာန်ဒေါဝ် (Edmund Landau) ဝွံ ဆက် ဇၞော်မောဝ် ကေုာံ ပြးဇး စကာ သင်္ကေတ ဏအ် ဗွဲမလှဲလး ရ။ ဟိုတ်ဂှ်ရ လဆောဝ် မ္ဂး ညးတအ် ကော်စ ဍေဟ် "သင်္ကေတ လာန်ဒေါဝ်" (Landau symbols) ရ။
စိုပ် ခေတ် ၁၉၇၀ တအ် ဂှ်၊ အစာ သုတေသန သိပ္ပံကောန်ပျူတာ ဒေါ်နယ် ခနုတ် (Donald Knuth) ဝွံ လွဳစကာ ကေတ် သင်္ကေတ ဏအ် နူကဵု သင်္ချာ သွက်ဂွံ စကာ ပ္ဍဲ ပရေင်သ္ၚေဝ်ဂၠေပ် အလ်ဂဝ်ရဳထမ် (Algorithm analysis) ရ။ ခနုတ် ဝွံ ထပ် ခၞံဗဒှ် လဝ် သင်္ကေတ မဆက်စပ် တၞဟ်ဂမၠိုင် မပ္တံကဵု $\Omega$ (အဝ်မေဂါ) ကေုာံ $\Theta$ (သဳတာ) ညံင်ဂွံ ကိတ်ညဳ ကု ပွံက်အဓိပ္ပါယ် သိပ္ပံကောန်ပျူတာ ရ။[၃]
၃။ သဇိုင် လဒက်ပတန် သင်္ချာ (Formal Mathematical Definition)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]နကဵု သၞောတ် သင်္ချာ ပွံက်အဓိပ္ပါယ် မချိုတ်ပၠိုတ် မ္ဂး၊ သင်္ကေတ အဝ် ဇၞော် ဝွံ ဗၟံက်ထ္ၜး လဝ် ပရေင်ဆက်စပ် အကြာ ဖန်ယှေန် ၜါ ရ။ ကဵု လဝ် ဖန်ယှေန် $f(n)$ ကေုာံ $g(n)$ ဂှ် ဒှ် ဖန်ယှေန် မနွံကဵု တန်ဖဵု ဓမ္မတာ (Positive functions) သွက် $n > 0$ မ္ဂး:
ပိုယ် ချူ $$f(n) = O(g(n))$$ (ဟီုမ္ဂး $f(n)$ ဒှ် အဝ် ဇၞော် ၏ $g(n)$)၊ ယဝ်ရ နွံကဵု လၟိဟ်တန် အလုံ (Positive constants) $c$ ကေုာံ $n_0$ တုဲ၊ သွက် ဇၟာပ်ဇၟာပ် $n \geq n_0$ မ္ဂး တန်ဖဵု ဖန်ယှေန် ဂှ် ကိတ်ညဳ ကု တင်သ္ဂုတ်သွာတ် ဗွဲသၟဝ်ဏအ် ရ - $$0 \leq f(n) \leq c \cdot g(n)$$
အဓိပ္ပါယ် ဍေဟ် ဂှ် လက္ကရဴ အိုတ် (ကာလ $n$ ဇၞော် တိုန် ဗွဲမလောန်) မ္ဂး၊ $f(n)$ ဂှ် ဟွံမာန် ဇၞော် တိုန် ပြဟ် နူကဵု သၞောတ် $g(n)$ (နကဵု လၟိဟ် ပတၟောအ် $c$) ရ။ အရာဏအ် ဝွံ ဒှ် ပရေင်ကဵု သမ္တီ သွက် "ပယျဵု လပါ်လတူ" (Upper bound) သွက် ပရေင်ဇၞော်မောဝ် (Growth rate) ရ။
၄။ ဂကောံ သင်္ကေတ အဓိကဂမၠိုင် (Common Orders of Big O)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပ္ဍဲကဵု သိပ္ပံကောန်ပျူတာ မ္ဂး၊ အလ်ဂဝ်ရဳထမ် တအ် ဂှ် ပါ်ကရေက် လဝ် နကဵု ဂကောံ (Classes) အတိုင် ပရေင်ချပ်ဂၞန် အခိင် ဍေဟ်တအ် ရ။ ဗွဲသၟဝ် ဏအ် ဒှ် သ္ၚိအင် (Table) ထ္ၜးလဝ် ဂကောံ သင်္ကေတ အဝ် ဇၞော် မပြာကတ် အိုတ် ဂမၠိုင် ရ။
| သင်္ကေတ (Notation) | ယၟု (Name) | ပွံက်အဓိပ္ပါယ် / ဗီုပြင် အကာဲအရာ | ဥပမာ အလ်ဂဝ်ရဳထမ် (Examples) |
|---|---|---|---|
| $O(1)$ | လၟိဟ်တန် (Constant) | အခိင် စကာ ဂှ် ဟွံပြံင်လှာဲ ရ၊ ဟွံဆက်စပ် ကု ဇမၞော် $n$။ လောဲသွာ အိုတ်။ | ဂၠာဲ တင်ဂၞင် ပ္ဍဲ Array အတိုင် ဒၞာဲ Index ဍေဟ်။ |
| $O(\log n)$ | လဝ်ဂရစ်ထမ် (Logarithmic) | အခိင် ဇၞော်တိုန် ညိည သၟး ကာလ $n$ ဇၞော် တိုန် ဗွဲမလောန်။ ပြဟ် လောန်။ | Binary search (ပရေင်ဂၠာဲ တင်ဂၞင် ပါ်ကရေက် ၜါ)။ |
| $O(n)$ | လဳနဳယာ (Linear) | အခိင် ဇၞော်တိုန် အတိုင် ဗီုပြင် တပ်တပ် ကု ဇမၞော် $n$။ | လ္ၚတ် ဗှ် တင်ဂၞင် သီုဖအိုတ် ပ္ဍဲ Array မွဲ။ Linear search။ |
| $O(n \log n)$ | လဳနဳရစ်ထမ် (Linearithmic) | ဇၞော် တိုန် ပြဟ် နူ $O(n)$ ဆဂး သဝ် နူ $O(n^2)$။ | Merge sort, Quick sort (အကာဲအရာ အဒေါဝ်)။ |
| $O(n^2)$ | ကွာဒရက်တစ် (Quadratic) | အခိင် ဇၞော်တိုန် အတိုင် $n$ ထပ်ဆ ၜါ။ ကေတ် အခိင် ဂၠိုင် သွက် $n$ ဇၞော်။ | Bubble sort, Insertion sort, ပရေင်စၟတ်သမ္တီ Nested loops ၜါ။ |
| $O(2^n)$ | အိက်သပဝ်နေန်ရှေယ် (Exponential) | အခိင် ဇၞော်တိုန် ကဵု ဆ ဗွဲမပြဟ် လောန်။ ဟွံခိုဟ် သွက် တင်ဂၞင် ဇၞော်။ | သောင်ကလး ပြသၞာ Tower of Hanoi, Recursive Fibonacci။ |
| $O(n!)$ | ဖက်တဝ်ရဳယယ် (Factorial) | အခိင် ဇၞော်တိုန် ပြဟ်အိုတ်။ ကောန်ပျူတာ သောင်ကလး ဟွံမာန် သွက် $n > 20$။ | ဂၠာဲ တရဴ သီုဖအိုတ် ပ္ဍဲ Traveling Salesperson Problem (Brute force)။ |
၅။ လွပ် ပ္ဍဲ သိပ္ပံကောန်ပျူတာ (Applications in Computer Science)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပ္ဍဲကဵု လၟေင်ကမၠောန် ချူ ပရဝ်ဂရာမ် ကေုာံ သုတေသန သိပ္ပံကောန်ပျူတာ ဂှ်၊ သင်္ကေတ အဝ် ဇၞော် ဝွံ ဒှ် အရေဝ်ဘာသာ ဓမ္မတာ (Lingua franca) သွက်ဂွံ ဓရီုကျာ ကေုာံ သ္ၚေဝ်ဂၠေပ် အလ်ဂဝ်ရဳထမ် ရ။
ကာလ တၠပညာ ကောန်ပျူတာ တအ် ဖန်ဗဒှ် သၞောတ် တၟိ (ဥပမာ - သၞောတ် ဂၠာဲ တင်ဂၞင် Google Search) မ္ဂး၊ ညးတအ် ဒးရုဲစှ် အလ်ဂဝ်ရဳထမ် မနွံကဵု အဝ် ဇၞော် မဍောတ် အိုတ် ရ။ ဟိုတ်နူကဵု ဒေတာ (Data) လတူ အင်တာနက် ဂှ် နွံ မဂၠိုင်ကဵု ဗဳလဳယာန် ဂှ်ရ၊ ယဝ်ရ စကာ အလ်ဂဝ်ရဳထမ် $O(n^2)$ မ္ဂး ကောန်ပျူတာ မဇၞော်အိုတ် လတူ ဂၠးတိ ဏအ် လေဝ် ကေတ် အခိင် မဂၠိုင် ကဵု သၞာံ သွက်ဂွံ တွက်ဂွံ သွဟ် ရ။ ဆဂး ယဝ်ရ စကာ အလ်ဂဝ်ရဳထမ် $O(\log n)$ မ္ဂး ဍေဟ် မာန် ကဵု သွဟ် ပ္ဍဲ အခိင် စက္က သၟး ရ။ အရာဏအ် ထ္ၜးကဵု ဒဒှ်ရ အလ်ဂဝ်ရဳထမ် မခိုဟ် ဂှ် ကိစ္စဇၞော် နူကဵု ဟာတ်ဝလ် မပြဟ် ရ။[၄]
၆။ ပရေင်ၜတ်ကၞာတ် အလ်ဂဝ်ရဳထမ် (Algorithm Analysis: Time and Space Complexity)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]သင်္ကေတ အဝ် ဇၞော် ဝွံ စကာ သွက်ဂွံ ၜတ်ကၞာတ် ကဏ္ဍ အဓိက ၜါ သာ် ပ္ဍဲ အလ်ဂဝ်ရဳထမ် -
- အခိင် ပရေင်ချပ်ဂၞန် (Time Complexity): ၜတ်ကၞာတ် ဒဒှ်ရ အလ်ဂဝ်ရဳထမ် မွဲ ဒးစကာ လၟေင်ကမၠောန် (Operations) ဂလိုင်လဵု သွက်ဂွံ စိုပ် တိုင်ပ္ကဴ ရ။ အရာဏအ် ဆက်စပ် ဒၟံင် ကု အစောံသတ္တိ CPU ရ။
- ဒၞာဲ ပရေင်ချပ်ဂၞန် (Space Complexity): ၜတ်ကၞာတ် ဒဒှ်ရ အလ်ဂဝ်ရဳထမ် မွဲ ဒးစကာ သမ္တီ တင်ဂၞင် (Memory / RAM) ဂလိုင်လဵု သွက်ဂွံ သောင်ကလး ပြသၞာ ရ။
လဆောဝ်မ္ဂး အလ်ဂဝ်ရဳထမ် လ္ၚဵု တအ် နွံကဵု ပရေင်ဖန်ဇန် အလန် (Trade-off) အကြာ အခိင် ကေုာံ ဒၞာဲ ရ။ ဥပမာ - ပရေင်စကာ ဒၞာဲ မှတ်ဉာဏ် ဂၠိုင်တိုန် (Space) ဂှ် မာန် ဖအောန် ဖျေဟ် အခိင် (Time) မာန် ရ။ သင်္ကေတ အဝ် ဇၞော် ဝွံ ကဵု အထံက်အပင် သွက်ဂွံ သ္ၚေဝ်ဂၠေပ် အကာဲအရာ သီု ၜါ လပါ် ဏအ် ရ။
၇။ သင်္ကေတ မဆက်စပ်ဂမၠိုင် (Related Asymptotic Notations)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပါဲနူကဵု သင်္ကေတ အဝ် ဇၞော် (Big O) မဒှ် အရာ မစၟတ်သမ္တီ "ပယျဵု လပါ်လတူ" (Upper bound) တုဲ၊ ပ္ဍဲကဵု တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (Computational complexity theory) ဂှ် နွံကဵု သင်္ကေတ တၞဟ်ဂမၠိုင် ကီု ရ -
- Big Omega ($\Omega$): စၟတ်သမ္တီ "ပယျဵု လပါ်သၟဝ်" (Lower bound)။ $f(n) = \Omega(g(n))$ ဟီုမ္ဂး $f(n)$ ဝွံ အောန်အိုတ် ဇၞော်တိုန် အတိုင် $g(n)$ ရ (ဍေဟ် ဟွံမာန် ပြဟ် နူ $g(n)$)။
- Big Theta ($\Theta$): စၟတ်သမ္တီ "ပယျဵု တုပ်သၟဟ်" (Tight bound)။ $f(n) = \Theta(g(n))$ ဟီုမ္ဂး $f(n)$ ဝွံ ဇၞော်တိုန် အတိုင် ဗီုပြင် $g(n)$ ကွက်တိ ရ (သီု လတူ သီု သၟဝ် တုပ် ရေင်သကအ်)။
- Little o ($o$): စၟတ်သမ္တီ ပယျဵု လပါ်လတူ မဟွံတုပ်သၟဟ် (Strict upper bound)။ $f(n) = o(g(n))$ ဟီုမ္ဂး $f(n)$ ဝွံ ဇၞော်တိုန် သဝ် နူ $g(n)$ တွဵု ရ။
- Little omega ($\omega$): စၟတ်သမ္တီ ပယျဵု လပါ်သၟဝ် မဟွံတုပ်သၟဟ် (Strict lower bound)။
၈။ ပရေင်သ္ၚေဝ်ဂၠေပ် အလ်ဂဝ်ရဳထမ် မပြာကတ် (Analysis of Common Algorithms)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]သွက်ဂွံ ကၠိုဟ်ခၠင် သင်္ကေတ ဏအ် လောဲသွာ၊ ဗွဲသၟဝ် ဏအ် ဒှ် ဥပမာ ပရေင်သ္ၚေဝ်ဂၠေပ် အလ်ဂဝ်ရဳထမ် မပြာကတ် ဂမၠိုင် ရ -
- Binary Search (ပရေင်ဂၠာဲ ပါ်ကရေက် ၜါ): ယဝ်ရ ပိုယ် နွံကဵု စရင် တင်ဂၞင် မစွံလဝ် အတိုင် လၟေင် (Sorted array) မ္ဂး၊ သွက်ဂွံ ဂၠာဲ တင်ဂၞင် မွဲမ ဂှ် ပိုယ် ပါ်ကရေက် လဒေါဝ် ဍေဟ် ဇၟာပ် အလန် ရ။ ဟိုတ်ဂှ်ရ ယဝ်ရ တင်ဂၞင် လၟိဟ် $n$ နွံ မ္ဂး၊ အခိင် ဒးစကာ ဂှ် ဒှ် $O(\log n)$ ရ။ အရာဏအ် ဝွံ ပြဟ် ဗွဲမလောန် ရ။
- Bubble Sort (ပရေင်ရုဲစှ် ထပ်ဆ): သွက်ဂွံ စွံ လၟေင် တင်ဂၞင် ဂှ် ဍေဟ် ၜတ်ကၞာတ် တင်ဂၞင် ၜါမ ဇၟာပ်ဇၟာပ် အလန် တုဲ ပြံင်လှာဲ ဒၞာဲ ရ။ ဟိုတ်နူကဵု ဍေဟ် ဒးလုပ် ဂေတ် ပ္ဍဲ လၟေင် $n$ ၜါ ဝါ (Nested loop) ဂှ်ရ၊ အခိင် ဍေဟ် ဒှ် $O(n^2)$ ရ။
- Merge Sort (ပရေင်ရုဲစှ် ပံင်ကောံ): ဍေဟ် ပါ်ကရေက် စရင် ဇၞော် ဂှ် ဒှ် စရင် ဍောတ်တ် ($O(\log n)$) တုဲ ကလေင် ပံင်ကောံ ဍေဟ်တအ် ဇၟာပ် မ ($O(n)$) ရ။ ဟိုတ်ဂှ်ရ အခိင် သီုဖအိုတ် ဒှ် $O(n \log n)$ ရ။[၅]
၉။ တင်ကန့်သတ် ကေုာံ အခက်အခုဲ (Limitations and Practical Considerations)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ၜိုန်ရ သင်္ကေတ အဝ် ဇၞော် ဝွံ ဒှ် အရာ မကိစ္စဇၞော် ကီုလေဝ်၊ ဍေဟ် နွံကဵု တင်ကန့်သတ် လ္ၚဵု တအ် ရ။
- လၟိဟ်တန် မပၞုက်လဝ် (Hidden Constants): သင်္ကေတ အဝ် ဇၞော် ဟွံစွံ အာရီု လတူ လၟိဟ်တန် ရ။ ဥပမာ - အလ်ဂဝ်ရဳထမ် မွဲ နွံကဵု အခိင် $1000n$ ကေုာံ မွဲပၠန် နွံကဵု အခိင် $2n$ မ္ဂး၊ ဍေဟ်တအ် သီု ၜါ ဂှ် ဒှ် $O(n)$ တုပ်တုပ် ရ။ ဆဂး ပ္ဍဲ လွပ် ဇေတ်တ် မ္ဂး ဒုတိယ မွဲ ဂှ် ပြဟ် နူ ၅၀၀ ဆ ဏီရ။
- လၟိဟ် တင်ဂၞင် ဍောတ် (Small Input Sizes): ယဝ်ရ လၟိဟ် $n$ ဂှ် ဍောတ် ဗွဲမလောန် (ဥပမာ $n = 10$) မ္ဂး၊ အလ်ဂဝ်ရဳထမ် $O(n^2)$ လဆောဝ် မ္ဂး ပြဟ် နူကဵု $O(n \log n)$ မာန် ရ (ဟိုတ်နူ Overhead ဍောတ်)။
- အကာဲအရာ မန်မဝ်ရဳ (Memory Hierarchy): သင်္ကေတ ဏအ် ဟွံသ္ၚေဝ်ဂၠေပ် ဗီုလဵု ကောန်ပျူတာ စွံ တင်ဂၞင် ပ္ဍဲ Cache vs RAM ရ။ လဆောဝ်မ္ဂး အလ်ဂဝ်ရဳထမ် မစကာ Cache ခိုဟ် (Cache locality) ဂှ် ပြဟ် နူကဵု အလ်ဂဝ်ရဳထမ် တဳအဝ်ရဳ မခိုဟ် ရ။
၁၀။ အနာဂတ် သုတေသန (Future Research and Advanced Topics)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပ္ဍဲကဵု သုတေသန ခေတ်တၟိ ဂှ်၊ တၠပညာ တအ် ဆက် ဇၞော်မောဝ် လညာတ် သင်္ကေတ အဝ် ဇၞော် သွက်ဂွံ သ္ၚေဝ်ဂၠေပ် အကာဲအရာ ကောန်ပျူတာ မနွံကဵု အစောံသတ္တိ နာနာ သာ် ရ။
- ပရေင်သ္ၚေဝ်ဂၠေပ် အမဝ်တိုက် (Amortized Analysis): လဆောဝ်မ္ဂး လၟေင်ကမၠောန် မွဲဝါ ဂှ် ကေတ် အခိင် ဂၠိုင် ($O(n)$) ဆဂး လၟေင်ကမၠောန် မဂၠိုင် ဂှ် ကေတ် အခိင် အောန် ($O(1)$) ရ။ Amortized analysis ၜတ်ကၞာတ် အခိင် လဒေါဝ် (Average time per operation) သွက် လၟေင်ကမၠောန် သီုဖအိုတ် ရ။
- အလ်ဂဝ်ရဳထမ် ကျပပန် (Randomized Algorithms): ပ္ဍဲ အလ်ဂဝ်ရဳထမ် သာ်ဏအ် (ဥပမာ Quick Sort) ဂှ် အခိင် မပရေအ်အိုတ် (Worst-case) ကေုာံ အခိင် လဒေါဝ် (Average-case) တအ် ဟွံတုပ် ရေင်သကအ် ရ။
- ကွမ်တမ် အလ်ဂဝ်ရဳထမ် (Quantum Algorithms): နကဵု ကွမ်တမ် ကောန်ပျူတာ (Quantum computing) ဂှ်၊ ပြသၞာ လ္ၚဵု တွက်ဂွံ နကဵု အခိင် $O(e^n)$ ပ္ဍဲ ကောန်ပျူတာ ဓမ္မတာ ဂှ် ပြံင်လှာဲ အာ နဒဒှ် $O(n^3)$ ပ္ဍဲ ကောန်ပျူတာ ကွမ်တမ် မာန် ရ (ဥပမာ Shor's Algorithm)။ [၆] အရာဏအ် ဖန်ဗဒှ် ကဵု ကဏ္ဍ တၟိ သွက် ပရေင်သ္ၚေဝ်ဂၠေပ် ပ္ဍဲ အနာဂတ် ရ။
နိဿဲဂမၠိုင်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- ↑ Cormen, T. H. (2009). Introduction to Algorithms, 3rd, MIT Press, 43-50။
- ↑ Bachmann, P. (1894). Analytische Zahlentheorie. B. G. Teubner, 400-405။
- ↑ Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd, Addison-Wesley, 104-108။
- ↑ Sipser, M. (2012). Introduction to the Theory of Computation, 3rd, Cengage Learning, 247-253။
- ↑ Kleinberg, J. (2005). Algorithm Design. Pearson, 41-45။
- ↑ Nielsen, M. A. (2010). Quantum Computation and Quantum Information, 10th Anniversary, Cambridge University Press, 216-220။
ဆက်ဗှ်လ္ၚတ်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- သိပ္ပံ ကောန်ပျူတာ (Computer science)
- အလ်ဂဝ်ရဳထမ် (Algorithm)
- အခိင် ကေုာံ ဒၞာဲ (Time and space complexity)
- တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (Computational complexity theory)