EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ

algorithm တစ်ခုလည်ပတ်ရန် လိုအပ်သော အရင်းအမြစ်ပမာဏ ပမာဏသည် input ၏ အရွယ်အစားနှင့် ကွဲပြားသောကြောင့်၊ ရှုပ်ထွေးမှုကို အများအားဖြင့် function f(n) အဖြစ် ဖော်ပြကြပြီး၊ n သည် input size ဖြစ်ပြီး f(n) သည် အဆိုးရွားဆုံး ရှုပ်ထွေးမှုဖြစ်နိုင်သည် ( size n ၏ သွင်းအားစုများအားလုံးတွင် လိုအပ်သော အရင်းအမြစ်အများဆုံးပမာဏ သို့မဟုတ် ပျမ်းမျှဖြစ်ရပ်မှန် ရှုပ်ထွေးမှု ( size n ၏ သွင်းအားစုအားလုံးထက် ပျမ်းမျှပမာဏ၏ အရင်းအမြစ်ပမာဏ)။ အရွယ်အစား n ၏ ထည့်သွင်းမှုတစ်ခုတွင် လိုအပ်သော အခြေခံလုပ်ဆောင်မှုအရေအတွက်ကို အချိန်ရှုပ်ထွေးမှုအဖြစ် ယေဘုယျအားဖြင့်ဖော်ပြထားပြီး မူလလုပ်ငန်းဆောင်တာများသည် ကွန်ပျူတာတစ်ခုပေါ်တွင် အချိန်အတိုင်းအတာတစ်ခုအထိကြာပြီး မတူညီသောစက်တစ်ခုပေါ်တွင် လုပ်ဆောင်သည့်အခါ အဆက်မပြတ်အချက်တစ်ချက်ဖြင့်သာ ပြောင်းလဲလေ့ရှိသည့် မူလလုပ်ငန်းဆောင်တာများကို အချိန်အတိုင်းအတာတစ်ခုအဖြစ် သတ်မှတ်ထားသည်။ size n တွင် ထည့်သွင်းသည့် algorithm တစ်ခုမှ လိုအပ်သော memory ပမာဏကို space complexity ဟုခေါ်သည်။

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

သမားရိုးကျ အချိန်ယူနစ်များ (စက္ကန့်၊ မိနစ်စသည်ဖြင့်) ကို ရှုပ်ထွေးမှုသီအိုရီတွင် အသုံးမချသောကြောင့် ၎င်းတို့သည် ကွန်ပျူတာရွေးချယ်မှုနှင့် နည်းပညာတိုးတက်မှုအပေါ် အလွန်အမင်း အားကိုးနေသောကြောင့် ဖြစ်သည်။ ဥပမာအားဖြင့်၊ ယနေ့ခေတ် ကွန်ပျူတာတစ်လုံးသည် 1960 ခုနှစ်များမှ ကွန်ပျူတာတစ်လုံးထက် များစွာမြန်ဆန်သော algorithm တစ်ခုကို လုပ်ဆောင်နိုင်သော်လည်း၊ ၎င်းသည် algorithm ၏ မွေးရာပါအရည်အသွေးထက် ကွန်ပျူတာ hardware တွင် နည်းပညာပိုင်းဆိုင်ရာ တိုးတက်မှုများကြောင့်ဖြစ်သည်။ ရှုပ်ထွေးမှုသီအိုရီ၏ ပန်းတိုင်မှာ အယ်လဂိုရီသမ်များ၏ မွေးရာပါအချိန်လိုအပ်ချက်များကို တွက်ချက်ရန် သို့မဟုတ် မည်သည့်ကွန်ပျူတာတွင်မဆို အယ်လဂိုရီသမ်တစ်ခုချမှတ်မည့် အခြေခံအချိန်ကန့်သတ်ချက်များကို တွက်ချက်ရန်ဖြစ်သည်။ တွက်ချက်မှုအတွင်း အခြေခံလုပ်ဆောင်မှု မည်မျှလုပ်ဆောင်သည်ကို ရေတွက်ခြင်းဖြင့် ၎င်းကို ပြီးမြောက်စေသည်။ ဤလုပ်ထုံးလုပ်နည်းများသည် စက်တစ်ခုတွင် အဆက်မပြတ်အချိန်ယူသည်ဟု ယူဆသောကြောင့် ၎င်းတို့ကို အဆင့်များဟု အများအားဖြင့် ရည်ညွှန်းသည် (ဆိုလိုသည်မှာ ၎င်းတို့သည် ထည့်သွင်းမှုပမာဏအားဖြင့် သက်ရောက်မှုမရှိပါ)။

နောက်ထပ်အရေးကြီးသောအရင်းအမြစ်မှာ algorithms လုပ်ဆောင်ရန်အတွက် ကွန်ပျူတာမှတ်ဉာဏ်ပမာဏဖြစ်သည်။

နောက်ထပ်အသုံးများသော အရင်းအမြစ်မှာ ဂဏန်းသင်္ချာလုပ်ငန်းဆောင်တာများဖြစ်သည်။ ဤအခြေအနေတွင်၊ "ဂဏန်းသင်္ချာရှုပ်ထွေးမှု" ဟူသော အသုံးအနှုန်းကို အသုံးပြုသည်။ အချိန်ရှုပ်ထွေးမှုသည် ယေဘူယျအားဖြင့် ကိန်းသေကိန်းဂဏန်းတစ်ခုဖြင့် ဂဏန်းသင်္ချာရှုပ်ထွေးမှု၏ ရလဒ်ဖြစ်သည်။

တွက်ချက်မှုတစ်ခုအတွင်း အသုံးပြုခဲ့သော ကိန်းပြည့်များ၏ အရွယ်အစားသည် နည်းလမ်းများစွာအတွက် ကန့်သတ်မထားဘဲ၊ ဂဏန်းသင်္ချာလုပ်ငန်းဆောင်တာများသည် သတ်မှတ်ထားသော အချိန်အတိုင်းအတာတစ်ခု လိုအပ်သည်ဟု ယူဆခြင်းသည် လက်တွေ့မကျပါ။ ရလဒ်အနေဖြင့်၊ bit complexity ဟုလည်းသိကြသော အချိန်ရှုပ်ထွေးမှုသည် ဂဏန်းသင်္ချာရှုပ်ထွေးမှုထက် သိသာစွာမြင့်မားနိုင်သည်။ ဥပမာအားဖြင့် nn integer matrix ၏ အဆုံးအဖြတ်ကို တွက်ချက်ရာတွင် ဂဏန်းသင်္ချာအခက်အခဲမှာ O(n^3) သည် စံနည်းပညာများ (Gaussian elimination) ဖြစ်သည်။ ကိန်းဂဏန်းများ၏ အရွယ်အစားသည် တွက်ချက်မှုအတွင်း အဆတိုးနိုင်သောကြောင့်၊ တူညီသောနည်းလမ်းများ၏ အနည်းငယ်ရှုပ်ထွေးမှုသည် n တွင် ကိန်းဂဏန်းများဖြစ်သည်။ ဤနည်းပညာများကို မော်ဂျူးဂဏန်းသင်္ချာပေါင်းများစွာနှင့် တွဲဖက်အသုံးပြုပါက၊ အနည်းငယ်ရှုပ်ထွေးမှုကို O(n^4) သို့ လျှော့ချနိုင်သည်။

bit complexity သည် algorithm တစ်ခုကို run ရန် လိုအပ်သော bit များဆိုင်ရာ လုပ်ဆောင်ချက် အရေအတွက်ကို ရည်ညွှန်းသည်။ ၎င်းသည် တွက်ချက်မှုဆိုင်ရာ ပရာဒိုင်းအများစုတွင် ကိန်းသေတစ်ခုအထိ ယာယီရှုပ်ထွေးမှုနှင့် ညီမျှသည်။ ကွန်ပြူတာများလိုအပ်သော စက်စကားလုံးများအတွက် လုပ်ဆောင်မှုအရေအတွက်သည် အနည်းငယ်ရှုပ်ထွေးမှုနှင့် အချိုးကျပါသည်။ လက်တွေ့ကျသော တွက်ချက်မှုပုံစံများအတွက်၊ အချိန်ရှုပ်ထွေးမှုနှင့် အနည်းငယ်ရှုပ်ထွေးမှုတို့သည် တူညီပါသည်။

စီစဥ်ခြင်းနှင့် ရှာဖွေခြင်းတွင် ထည့်သွင်းစဉ်းစားလေ့ရှိသော အရင်းအမြစ်မှာ ထည့်သွင်းမှုများ နှိုင်းယှဉ်မှုပမာဏဖြစ်သည်။ ဒေတာကို ကောင်းစွာစီစဉ်ထားပါက၊ ၎င်းသည် အချိန်ရှုပ်ထွေးမှု၏ ကောင်းသောညွှန်ပြချက်ဖြစ်သည်။

ဖြစ်နိုင်ချေရှိသော သွင်းအားစုများအားလုံးတွင်၊ algorithm တစ်ခုရှိ အဆင့်အရေအတွက်ကို ရေတွက်ရန် မဖြစ်နိုင်ပါ။ input တစ်ခု၏ ရှုပ်ထွေးမှုသည် ၎င်း၏ အရွယ်အစားနှင့် တိုးလာသောကြောင့် ၎င်းကို input ၏ size n (bits) ၏ function အဖြစ် ကိုယ်စားပြုပြီး ရှုပ်ထွေးမှုသည် n ၏ function တစ်ခုဖြစ်သည်။ အရွယ်အစားတူ သွင်းအားစုများအတွက်၊ အယ်လဂိုရီသမ်တစ်ခု၏ ရှုပ်ထွေးမှုသည် သိသိသာသာ ကွဲပြားနိုင်သည်။ ရလဒ်အနေဖြင့်၊ ရှုပ်ထွေးမှုအမျိုးမျိုးသော လုပ်ငန်းဆောင်တာများကို ပုံမှန်အသုံးပြုကြသည်။

အဆိုးဆုံးသော ရှုပ်ထွေးမှုသည် အရွယ်အစား n သွင်းအားစုအားလုံးအတွက် ရှုပ်ထွေးမှုအားလုံး၏ ပေါင်းစုဖြစ်ပြီး ပျမ်းမျှကိစ္စရပ်ရှုပ်ထွေးမှုသည် အရွယ်အစား n သွင်းအားစုအားလုံးအတွက် ရှုပ်ထွေးမှုအားလုံး၏ ပေါင်းလဒ်ဖြစ်သည် (၎င်းသည် ပေးထားသည့် အရွယ်အစား၏ ဖြစ်နိုင်ချေရှိသော သွင်းအားစုများ၏ အရေအတွက်ဖြစ်သောကြောင့်၊ ဆိုလိုသည်မှာ အဓိပ္ပာယ်မှာ၊ အကန့်အသတ်)။ “ရှုပ်ထွေးမှု” ဟူသောအသုံးအနှုန်းကို ထပ်မံမသတ်မှတ်ဘဲ အသုံးပြုသောအခါ၊ အဆိုးဆုံးအချိန်ရှုပ်ထွေးမှုကို ထည့်သွင်းစဉ်းစားသည်။

အဆိုးဆုံးနှင့် သာမန်ကိစ္စများ ရှုပ်ထွေးမှုသည် မှန်ကန်စွာ တွက်ချက်ရန် နာမည်ဆိုးဖြင့် ကျော်ကြားသည်။ ထို့အပြင်၊ စက် သို့မဟုတ် တွက်ချက်မှုဆိုင်ရာ ပါရာဒိုင်းတွင် ပြောင်းလဲမှုတိုင်းသည် ရှုပ်ထွေးမှုအနည်းငယ်ကွဲပြားနိုင်သောကြောင့် အဆိုပါအတိအကျတန်ဖိုးများသည် လက်တွေ့အသုံးချမှုအနည်းငယ်သာရှိသည်။ ထို့အပြင် n ၏သေးငယ်သောတန်ဖိုးများအတွက် အရင်းအမြစ်အသုံးပြုမှုသည် အရေးမကြီးပါ၊ ထို့ကြောင့် အကောင်အထည်ဖော်ရာတွင် လွယ်ကူမှုသည် n အသေးစားအတွက် ရှုပ်ထွေးမှုနည်းပါးသည်ထက် ပိုမိုနှစ်သက်ဖွယ်ကောင်းသည်။

ဤအကြောင်းများကြောင့်၊ n သည် အဆုံးမရှိချဉ်းကပ်လာသည်နှင့်အမျှ ၎င်း၏ asymptotic အပြုအမူသည် မြင့်မားသော ရှုပ်ထွေးမှုအတွက် အာရုံစိုက်မှုအများဆုံးဖြစ်သည်။ ရလဒ်အနေဖြင့် ကြီးမားသော O notation ကို ရှုပ်ထွေးမှုကို ဖော်ပြရန်အတွက် အများအားဖြင့် အသုံးပြုကြသည်။

ကွန်ပြူတာမော်ဒယ်များ

အချိန်ယူနစ်တစ်ခုအတွင်း လုပ်ဆောင်ရမည့် မရှိမဖြစ်လိုအပ်သော လုပ်ဆောင်ချက်များကို သတ်မှတ်ခြင်း ပါဝင်သော တွက်ချက်မှုပုံစံတစ်ခု၏ ရွေးချယ်မှုသည် ရှုပ်ထွေးမှုကို ဆုံးဖြတ်ရာတွင် အရေးကြီးပါသည်။ တွက်ချက်မှုဆိုင်ရာ ပါရာဒိုင်းကို အထူးတလည် မဖော်ပြထားသောအခါ ၎င်းကို multitape Turing machine ဟုခေါ်သည်။

အဆုံးအဖြတ်ပေးသော တွက်ချက်မှုပုံစံသည် စက်၏နောက်ဆက်တွဲအခြေအနေများနှင့် လုပ်ဆောင်ရမည့်လုပ်ဆောင်ချက်များကို ယခင်အခြေအနေက လုံးလုံးလျားလျားသတ်မှတ်ထားသည်။ Recursive functions၊ lambda calculus နှင့် Turing machines များသည် ပထမဆုံးသော အဆုံးအဖြတ်ပေးသော မော်ဒယ်များဖြစ်သည်။ Random-access machines (RAM-machines ဟုလည်းခေါ်သည်) သည် ကမ္ဘာပေါ်ရှိ ကွန်ပျူတာများကို အတုယူရန်အတွက် ရေပန်းစားသော ပါရာဒိုင်းတစ်ခုဖြစ်သည်။

တွက်ချက်မှုပုံစံကို မသတ်မှတ်ထားသောအခါ၊ တိပ် Turing စက်ကို အများအားဖြင့် ယူဆသည်။ Multitape Turing စက်များတွင်၊ အချိန်ရှုပ်ထွေးမှုသည် algorithms အများစုအတွက် RAM စက်များကဲ့သို့ပင်ဖြစ်ပြီး၊ ဤညီမျှမှုကိုရရှိရန် ဒေတာသိမ်းဆည်းပုံအား မှတ်ဉာဏ်တွင် မှတ်သားထားရန် လိုအပ်သော်လည်း များစွာအာရုံစိုက်နိုင်ပါသည်။

သတ်မှတ်ထားသောမဟုတ်သော Turing စက်များကဲ့သို့သော အဆုံးအဖြတ်မရှိသော တွက်ချက်မှုပုံစံတွင် တွက်ချက်မှုအဆင့်အချို့တွင် အမျိုးမျိုးသောရွေးချယ်မှုများကို ပြုလုပ်နိုင်သည်။ ရှုပ်ထွေးမှုသီအိုရီတွင်၊ ဖြစ်နိုင်ခြေရှိသော ရွေးချယ်မှုများအားလုံးကို တစ်ချိန်တည်းတွင် ထည့်သွင်းစဉ်းစားပြီး အကောင်းဆုံးရွေးချယ်မှုများ အမြဲတမ်းပြုလုပ်သောအခါတွင် သတ်မှတ်ပြဋ္ဌာန်းချက်မရှိသော အချိန်ရှုပ်ထွေးမှုသည် လိုအပ်သည့်အချိန်ပမာဏဖြစ်သည်။ အခြားနည်းဖြင့်ပြောရလျှင် လိုအပ်သလောက် (တူညီသော) ပရိုဆက်ဆာများပေါ်တွင် တွက်ချက်ခြင်းအား တစ်ပြိုင်နက်တည်း လုပ်ဆောင်ပြီး အဆုံးအဖြတ်မရှိသော တွက်ချက်မှုအချိန်သည် တွက်ချက်မှု အပြီးသတ်ရန် ပထမပရိုဆက်ဆာမှ ယူသောအချိန်ဖြစ်သည်။ ဥပမာအားဖြင့် Shor ၏သေးငယ်သော integers များကို အပိုင်းပိုင်းခွဲခြင်းကဲ့သို့သော အထူးပြုကွမ်တမ် အယ်လဂိုရီသမ်များကို လုပ်ဆောင်သောအခါတွင် မျဉ်းပြိုင်ဖြစ်နေသော ကွမ်တမ်ကွန်ပြူတာတွင် ဤမျဉ်းပြိုင်စနစ်ကို အသုံးပြုနိုင်သည်။

ဤကဲ့သို့သော တွက်ချက်မှုပုံစံကို လောလောဆယ် လက်တွေ့မလုပ်ဆောင်နိုင်သေးပါက၊ အထူးသဖြင့် P = NP ပြဿနာနှင့်စပ်လျဉ်း၍ ၎င်းတွင် သီအိုရီဆိုင်ရာ အရေးပါမှုရှိပြီး၊ "polynomial time" နှင့် "သတ်မှတ်မဟုတ်သော polynomial time" ကိုအသုံးပြုခြင်းဖြင့် ထုတ်လုပ်သော ရှုပ်ထွေးမှုအတန်းများကို အထက်ပိုင်းအဖြစ် မေးသော၊ ဘောင်တွေက အတူတူပါပဲ။ အဆုံးအဖြတ်ပေးသောကွန်ပြူတာတွင်၊ NP-algorithm ကို အတုယူရန် "exponential time" လိုအပ်သည်။ အလုပ်တစ်ခုအား အဆုံးအဖြတ်မရှိသောစနစ်တွင် ပေါလီအမည်အချိန်အတွင်း ဖြေရှင်းနိုင်လျှင် ၎င်းသည် NP ခက်ခဲမှုအတန်းအစားဖြစ်သည်။ ပြဿနာတစ်ခုသည် NP တွင်ရှိပြီး အခြား NP ပြဿနာထက် မလွယ်ကူပါက၊ ၎င်းသည် NP-ပြီးပြည့်စုံသည်ဟု ဆိုသည်။ Knapsack ပြဿနာ၊ ခရီးသွားအရောင်းသမား ပြဿနာနှင့် Boolean ကျေနပ်နိုင်မှု ပြဿနာတို့သည် NP-ပြီးပြည့်စုံသော ပေါင်းစပ်ပြဿနာများဖြစ်သည်။ လူသိအများဆုံး အယ်လဂိုရီသမ်တွင် ဤပြဿနာအားလုံးအတွက် ကိန်းဂဏန်း ရှုပ်ထွေးမှုရှိသည်။ အကယ်၍ ဤပြဿနာများထဲမှ တစ်ခုခုကို အဆုံးအဖြတ်စက်တစ်ခုပေါ်တွင် ပေါလီအမည်အချိန်အတွင်း ဖြေရှင်းနိုင်ပါက၊ NP ပြဿနာအားလုံးကို ပေါင်းကိန်းအချိန်အတွင်းလည်း ဖြေရှင်းနိုင်ပြီး P = NP ကို ​​တည်ထောင်မည်ဖြစ်သည်။ 2017 ခုနှစ်အရ၊ NP ပြဿနာများ၏ အဆိုးဆုံးအခြေအနေများသည် ဖြေရှင်းရန်အခြေခံအားဖြင့် ခက်ခဲသည်ဟု ဆိုလိုသည်မှာ၊ စိတ်ဝင်စားစရာကောင်းသောထည့်သွင်းမှုအရှည်များပေးထားသော ဖြစ်နိုင်ချေရှိသော အချိန်ကာလ (ဆယ်စုနှစ်များ) ထက် ပိုမိုကြာမြင့်သည်ဟု XNUMX ခုနှစ်၌ ကျယ်ပြန့်စွာယူဆပါသည်။

မျဉ်းပြိုင်နှင့် ဖြန့်ဝေထားသော တွက်ချက်မှု

မျဉ်းပြိုင်နှင့် ဖြန့်ဝေထားသော တွက်ချက်မှုတွင် ပရိုဆက်ဆာများစွာကို တစ်ပြိုင်နက်တည်း လုပ်ဆောင်သည့် ပရိုဆက်ဆာအများအပြားကို ပိုင်းခြားခြင်းပါဝင်သည်။ မော်ဒယ်အမျိုးမျိုးအကြား အခြေခံကွဲပြားချက်မှာ ပရိုဆက်ဆာများကြားတွင် ဒေတာပေးပို့သည့်နည်းလမ်းဖြစ်သည်။ ပရိုဆက်ဆာများကြား ဒေတာပေးပို့ခြင်းသည် အများအားဖြင့် အပြိုင်ကွန်ပြူတာတွင် အလွန်လျင်မြန်သော်လည်း၊ ပရိုဆက်ဆာများအကြား ဖြန့်ဝေထားသော ကွန်ပြူတာတွင် ဒေတာလွှဲပြောင်းခြင်းမှာ ကွန်ရက်တစ်ခုပေါ်တွင် လုပ်ဆောင်ပြီးဖြစ်သောကြောင့် သိသိသာသာ နှေးကွေးပါသည်။

N ပရိုဆက်ဆာများတွင် တွက်ချက်မှုတစ်ခုသည် ပရိုဆက်ဆာတစ်ခုတည်းတွင်အသုံးပြုသည့်အချိန်၏ N မှ quotient ကို အနည်းဆုံးယူသည်။ လက်တွေ့တွင်၊ အချို့သောအလုပ်ခွဲများကို ပြိုင်တူမလုပ်ဆောင်နိုင်သောကြောင့် အချို့သောပရိုဆက်ဆာများသည် အခြားသောပရိုဆက်ဆာမှရလဒ်ကိုစောင့်ဆိုင်းရန် လိုအပ်နိုင်သောကြောင့်၊ ဤသီအိုရီအရ စံနမူနာထုပ်ပိုးခြင်းကို မည်သည့်အခါမျှ ရရှိနိုင်မည်မဟုတ်ပေ။

အဓိကရှုပ်ထွေးမှုပြဿနာမှာ ပရိုဆက်ဆာတစ်ခုတည်းတွင် တူညီသောတွက်ချက်မှုလုပ်ဆောင်ရန် လိုအပ်သည့်အချိန်နှင့် တွက်ချက်ချိန်ကိုက်သည့်အချိန်နှင့် ပရိုဆက်ဆာအရေအတွက်အလိုက် တွက်ချက်ခြင်း၏ထုတ်ကုန်ကို တတ်နိုင်သမျှနီးစပ်စေရန် အယ်လဂိုရီသမ်များကို တီထွင်ရန်ဖြစ်သည်။

ကွမ်တမ်တွက်ချက်မှု

ကွမ်တမ်ကွန်ပြူတာသည် ကွမ်တမ်မက္ကင်းနစ်ဆိုင်ရာ တွက်ချက်မှုပုံစံပါရှိသော ကွန်ပျူတာဖြစ်သည်။ Church-Turing thesis သည် ကွမ်တမ်ကွန်ပြူတာများအတွက် မှန်ကန်ကြောင်း အခိုင်အမာဆိုသည်၊ ကွမ်တမ်ကွန်ပြူတာသည် ဖြေရှင်းနိုင်သည့် မည်သည့်ပြဿနာကိုမဆို Turing စက်ဖြင့် ဖြေရှင်းနိုင်သည်ဟု ဆိုလိုသည်။ သို့သော်၊ အချို့သောအလုပ်များသည် သီအိုရီအရ သိသိသာသာနိမ့်ကျရှုပ်ထွေးမှုရှိသော ရှေးရိုးကွန်ပျူတာထက် ကွမ်တမ်ကွန်ပျူတာကို အသုံးပြု၍ ဖြေရှင်းနိုင်သည်။ လက်ရှိတွင်၊ လက်တွေ့ကျသော ကွမ်တမ်ကွန်ပြူတာအား မည်သို့တီထွင်ရမည်ကို မည်သူမျှ မသိသောကြောင့်၊ ၎င်းသည် သီအိုရီအရ တင်းကြပ်စွာ မှန်ကန်ပါသည်။

ကွမ်တမ်ကွန်ပြူတာများဖြင့် ဖြေရှင်းနိုင်သော မတူညီသောပြဿနာများကို စုံစမ်းစစ်ဆေးရန် ကွမ်တမ်ရှုပ်ထွေးမှုသီအိုရီကို ဖန်တီးခဲ့ခြင်းဖြစ်သည်။ ၎င်းကို ကွမ်တမ်ကွန်ပြူတာ တိုက်ခိုက်မှုများကို ခံနိုင်ရည်ရှိသော ကွမ်တမ်ကွန်ပြူတာ တိုက်ခိုက်မှုများကို ခံနိုင်ရည်ရှိသော ကွမ်တမ် ပရိုတိုကောများ ဖန်တီးခြင်း လုပ်ငန်းစဉ်ဖြစ်သည့် Post-quantum cryptography တွင် အသုံးပြုသည်။

ပြဿနာ၏ ရှုပ်ထွေးမှု (အောက်ခြေဘောင်များ)

မဖော်ထုတ်နိုင်သော နည်းပညာများ အပါအဝင် ပြဿနာကို ဖြေရှင်းနိုင်သည့် အယ်လဂိုရီသမ်များ၏ ရှုပ်ထွေးမှု အနိမ့်ဆုံးမှာ ပြဿနာ၏ ရှုပ်ထွေးမှုဖြစ်သည်။ ရလဒ်အနေဖြင့် ပြဿနာတစ်ခု၏ ရှုပ်ထွေးမှုသည် ၎င်းကိုဖြေရှင်းပေးသည့် မည်သည့် algorithm ၏ ရှုပ်ထွေးမှုနှင့် ညီမျှသည်။

ရလဒ်အနေဖြင့်၊ ကြီးမားသော O အမှတ်အသားတွင် ပေးထားသည့် ရှုပ်ထွေးမှုမှန်သမျှသည် အယ်လဂိုရီသမ်နှင့် ဆက်စပ်ပြဿနာနှစ်ခုစလုံး၏ ရှုပ်ထွေးမှုကို ကိုယ်စားပြုသည်။

အခြားတစ်ဖက်တွင်၊ ပြဿနာရှုပ်ထွေးမှုတွင် အသေးအဖွဲမဟုတ်သော အောက်ခြေနယ်နိမိတ်များကို ရယူရန်မှာ မကြာခဏ ခက်ခဲလေ့ရှိပြီး ထိုသို့ပြုလုပ်ရန်အတွက် နည်းဗျူဟာ အနည်းငယ်သာရှိသည်။

ပြဿနာအများစုကိုဖြေရှင်းရန်အတွက်၊ အချက်အလက်၏အတိုင်းအတာနှင့်အချိန်ယူ၍ ထည့်သွင်းထားသောဒေတာအားလုံးကိုဖတ်ရပါမည်။ ရလဒ်အနေဖြင့်၊ ထိုပြဿနာများသည် အနည်းဆုံး linear complexity သို့မဟုတ် Ω(n) ၏ ရှုပ်ထွေးမှုကြီးတွင် အိုမီဂါအမှတ်အသားတွင် ရှိသည်။

ကွန်ပျူတာ အက္ခရာသင်္ချာနှင့် တွက်ချက်မှုဆိုင်ရာ အက္ခရာသင်္ချာဂျီသြမေတြီကဲ့သို့သော အချို့ပြဿနာများသည် အလွန်ကြီးမားသော ဖြေရှင်းနည်းများရှိသည်။ အထွက်ကို ရေးရမည်ဖြစ်သောကြောင့်၊ အထွက်၏ အမြင့်ဆုံးအရွယ်အစားဖြင့် ရှုပ်ထွေးမှုကို ကန့်သတ်ထားသည်။

စီစဥ်သည့် အယ်လဂိုရီသမ်အတွက် လိုအပ်သော နှိုင်းယှဉ်မှုအရေအတွက်သည် Ω(nlogn) ၏ အောက်လိုင်းမဟုတ်သော ဘောင်တစ်ခုရှိသည်။ ရလဒ်အနေဖြင့်၊ ၎င်းတို့၏ ရှုပ်ထွေးမှုသည် O(nlogn) ဖြစ်သောကြောင့် အကောင်းဆုံး စီခြင်း အယ်လဂိုရီသမ်များသည် အထိရောက်ဆုံးဖြစ်သည်။ n ရှိပါတယ်ဆိုတဲ့အချက်ကို! n အရာများကို စုစည်းရန် နည်းလမ်းများသည် ဤအောက်ပိုင်းဘောင်သို့ ဦးတည်သည်။ နှိုင်းယှဉ်မှုတစ်ခုစီသည် ဤစုစည်းမှု n ကို ပိုင်းခြားထားသောကြောင့်ဖြစ်သည်။ အမှာစာများအားလုံးကို ပိုင်းခြားရန် လိုအပ်သော N နှိုင်းယှဉ်မှု အရေအတွက်သည် 2N > n! ဖြစ်ပြီး၊ Stirling ၏ဖော်မြူလာအရ O(nlogn) ကို ဆိုလိုသည်။

ပြဿနာတစ်ခုကို အခြားပြဿနာတစ်ခုသို့ လျှော့ချခြင်းသည် လျှော့ပေါ့ရှုပ်ထွေးမှု ကန့်သတ်ချက်များကို ရရှိရန် ဘုံဗျူဟာတစ်ခုဖြစ်သည်။

Algorithm ဖွံ့ဖြိုးတိုးတက်ရေး

အယ်လဂိုရီသမ်တစ်ခု၏ ရှုပ်ထွေးမှုကို အကဲဖြတ်ခြင်းသည် မျှော်လင့်နိုင်သည့် စွမ်းဆောင်ရည်နှင့်ပတ်သက်သော အသုံးဝင်သော အချက်အလက်များကို ပေးဆောင်သောကြောင့် ဒီဇိုင်းလုပ်ငန်းစဉ်၏ အရေးကြီးသောအစိတ်အပိုင်းတစ်ခုဖြစ်သည်။

ခေတ်မီကွန်ပြူတာပါဝါကြီးထွားမှုကို ခန့်မှန်းသည့် Moore ၏ဥပဒေကြောင့် ရှုပ်ထွေးသော အယ်လဂိုရီသမ်များကို အကဲဖြတ်ခြင်းသည် မကြာခဏနားလည်မှုလွဲမှားခြင်းတစ်ခုဖြစ်သည်။ တိုးမြှင့်ပါဝါသည် များပြားလှသော ဒေတာပမာဏ (ဒေတာကြီး) ကို လုပ်ဆောင်နိုင်သောကြောင့် ၎င်းသည် မမှန်ပါ။ ဥပမာအားဖြင့်၊ စာအုပ်တစ်အုပ်၏ bibliography ကဲ့သို့သော ရာနှင့်ချီသော entry များစာရင်းကို အက္ခရာစဉ်အလိုက်စီထားသောအခါ မည်သည့် algorithm မဆို ကောင်းမွန်စွာလုပ်ဆောင်နိုင်မည်ဖြစ်သည်။ အခြားတစ်ဖက်တွင်၊ ထည့်သွင်းမှုတစ်သန်း (ဥပမာ၊ မြို့ကြီးတစ်ခု၏ ဖုန်းနံပါတ်များ) အတွက် O(n2) နှိုင်းယှဉ်မှုများ လိုအပ်သည့် အခြေခံ algorithms သည် ထရီလျံနှိုင်းယှဉ်မှုများကို လုပ်ဆောင်ရမည်ဖြစ်ပြီး 10 အမြန်နှုန်းဖြင့် သုံးနာရီကြာမည်ဖြစ်သည်။ တစ်စက္ကန့်လျှင် သန်းနှိုင်းယှဥ်မှု။ အခြားတစ်ဖက်တွင်၊ Quicksort နှင့် ပေါင်းစည်းခြင်းအမျိုးအစားသည် nlogn နှိုင်းယှဉ်မှုများသာ လိုအပ်သည် (ယခင်အတွက် ပျမ်းမျှဖြစ်ရပ်မှန်ရှုပ်ထွေးမှု၊ နောက်တစ်ခုအတွက် အဆိုးဆုံးသောရှုပ်ထွေးမှုအဖြစ်)။ ၎င်းသည် n = 30,000,000 အတွက် နှိုင်းယှဉ်မှု 1,000,000 ဝန်းကျင်ကို ထုတ်ပေးမည်ဖြစ်ပြီး၊ တစ်စက္ကန့်လျှင် နှိုင်းယှဉ်မှု 3 သန်းတွင် 10 စက္ကန့်သာ ကြာမည်ဖြစ်သည်။

ရလဒ်အနေဖြင့်၊ ရှုပ်ထွေးမှုကို အကဲဖြတ်ခြင်းသည် အကောင်အထည်မဖော်မီ ထိရောက်မှုမရှိသော အယ်လဂိုရီသမ်များစွာကို ဖယ်ရှားနိုင်မည်ဖြစ်သည်။ ဖြစ်နိုင်ချေရှိသော မူကွဲအားလုံးကို စမ်းသပ်စရာမလိုဘဲ ရှုပ်ထွေးသော အယ်လဂိုရီသမ်များကို ကောင်းစွာချိန်ညှိရန်အတွက်လည်း ၎င်းကို အသုံးပြုနိုင်သည်။ ရှုပ်ထွေးမှုကို လေ့လာခြင်းသည် ရှုပ်ထွေးသော အယ်လဂိုရီသမ်တစ်ခု၏ ကုန်ကျစရိတ်အများဆုံးအဆင့်များကို ဆုံးဖြတ်ခြင်းဖြင့် အကောင်အထည်ဖော်မှုတစ်ခု၏ ထိရောက်မှုကို တိုးမြှင့်ရန် အားထုတ်မှုကို အာရုံစိုက်နိုင်စေသည်။