EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري اساسات

ځکه چې د الګوریتم چلولو لپاره د سرچینو مقدار د ان پټ د اندازې سره توپیر لري، پیچلتیا معمولا د فنکشن f(n) په توګه څرګندیږي، چیرې چې n د ان پټ اندازه ده او f (n) یا د خورا خراب حالت پیچلتیا ده ( د منابعو اعظمي مقدار چې د n اندازې په ټولو آخذونو کې اړین دي) یا د اوسط قضیې پیچلتیا (د منابعو مقدار اوسط د اندازې n ټولو داخلونو کې). د n اندازې په ان پټ کې د اړتیا وړ لومړني عملیاتو شمیر معمولا د وخت پیچلتیا په توګه ویل کیږي ، چیرې چې لومړني عملیات په یو ځانګړي کمپیوټر کې دوامداره وخت نیسي او یوازې د ثابت فاکتور لخوا بدلیږي کله چې په مختلف ماشین کې چلیږي. د حافظې مقدار چې د الګوریتم لخوا د اندازې n ان پټ کې اړین دی د ځای پیچلتیا په نوم پیژندل کیږي.

وخت ترټولو معمول ګڼل کیږي سرچینه ده. کله چې د "پیچلتیا" اصطلاح د وړتیا پرته کارول کیږي، دا معمولا د وخت پیچلتیا ته اشاره کوي.

د وخت دودیز واحدونه (ثانوي، دقیقې، او داسې نور) د پیچلتیا تیوري کې کار نه کوي ځکه چې دوی په غوره شوي کمپیوټر او د ټیکنالوژۍ پرمختګ باندې ډیر تکیه کوي. د مثال په توګه، نن ورځ یو کمپیوټر کولی شي د 1960 لسیزې راهیسې د کمپیوټر په پرتله خورا ګړندی الګوریتم اجرا کړي ، مګر دا د کمپیوټر هارډویر کې د ټیکنالوژیکي پرمختګونو له امله دی نه د الګوریتم اصلي کیفیت. د پیچلتیا تیوري هدف د الګوریتم د اصلي وخت اړتیاو اندازه کول دي، یا د وخت بنسټیز محدودیتونه چې یو الګوریتم به په کوم کمپیوټر باندې تطبیق کړي. دا د شمیرلو په واسطه سرته رسیږي چې د محاسبې په جریان کې څومره لومړني عملیات ترسره کیږي. دا پروسیجرونه عموما د ګامونو په توګه راجع کیږي ځکه چې دوی په یو ځانګړي ماشین کې دوامداره وخت نیسي (د بیلګې په توګه، دوی د ننوتلو مقدار څخه اغیزمن ندي).

بله مهمه سرچینه د کمپیوټر حافظې مقدار دی چې د الګوریتم ترسره کولو لپاره اړین دي.

بله اکثره کارول شوې سرچینه د ریاضیاتي عملیاتو اندازه ده. په دې سناریو کې، د "ریاضي پیچلتیا" اصطلاح کارول کیږي. د وخت پیچلتیا عموما د ریاضي پیچلتیا محصول دی چې د ثابت فاکتور لخوا رامینځته کیږي که چیرې د شمیرو د بائنری نمایش په اندازې کې پورتنۍ محدودیت پیژندل کیږي چې د محاسبې پرمهال پیښیږي.

د عددونو اندازه چې د محاسبې په جریان کې کارول کیږي د ډیری میتودونو لپاره محدود ندي، او دا غیر واقعیت دی چې فرض کړئ چې د ریاضي عملیات یو ټاکلي وخت ته اړتیا لري. د پایلې په توګه، د وخت پیچلتیا، چې د بټ پیچلتیا په نوم هم پیژندل کیږي، ممکن د ریاضیاتي پیچلتیا څخه د پام وړ لوړ وي. د nn انټیجر میټرکس د ټاکلو محاسبه ریاضي مشکل، د بیلګې په توګه، د معیاري تخنیکونو لپاره O(n^3) دی (ګاوسیان له منځه وړل). ځکه چې د کوفیفینټ اندازه ممکن د محاسبې په جریان کې په ګړندۍ توګه پراخه شي ، د ورته میتودونو لږ پیچلتیا په n کې کفایتي ده. که دا تخنیکونه د څو ماډلر ریاضیاتو سره په ګډه وکارول شي، د بټ پیچلتیا کیدای شي O(n^4) ته راټیټ شي.

د بټ پیچلتیا، په رسمي شرایطو کې، د الګوریتم چلولو لپاره اړین بټونو کې د عملیاتو شمیر ته اشاره کوي. دا د لنډمهاله پیچلتیا سره په ډیری محاسبه تمثیلونو کې ثابت فاکتور ته مساوي کوي. د کمپیوټر لخوا اړین ماشین کلمو باندې د عملیاتو شمیر د بټ پیچلتیا سره متناسب دی. د محاسبې د ریښتیني ماډلونو لپاره، د وخت پیچلتیا او لږ پیچلتیا په دې توګه ورته دي.

هغه سرچینې چې ډیری وختونه په ترتیب او لټون کې په پام کې نیول کیږي د ننوتونو پرتله کولو مقدار دی. که معلومات په ښه توګه تنظیم شوي وي، دا د وخت پیچلتیا ښه شاخص دی.

په ټولو احتمالي معلوماتو کې، په الګوریتم کې د ګامونو شمیرل ناممکن دي. ځکه چې د ان پټ پیچلتیا د هغې د اندازې سره لوړیږي، دا عموما د ان پټ د اندازې n (بټونو کې) د فعالیت په توګه ښودل کیږي، او له همدې امله پیچلتیا د n فعالیت دی. په هرصورت، د ورته اندازې معلوماتو لپاره، د الګوریتم پیچلتیا کیدای شي د پام وړ توپیر ولري. د پایلې په توګه، د پیچلتیا مختلف فعالیتونه په منظمه توګه کارول کیږي.

د بدترین حالت پیچلتیا د ټولو سایز n داخلونو لپاره د ټولو پیچلتیا مجموعه ده، پداسې حال کې چې د اوسط قضیې پیچلتیا د ټولو سایز n ان پټونو لپاره د ټولو پیچلتیا مجموعه ده (دا معنی لري، ځکه چې د ورکړل شوي اندازې د ممکنه معلوماتو شمیره ده. محدود). کله چې د "پیچلتیا" اصطالح پرته له دې چې نور تعریف شي کارول کیږي، د بدترین حالت وخت پیچلتیا په پام کې نیول کیږي.

د بدې قضیې او اوسط قضیې پیچلتیا په سمه توګه محاسبه کول خورا ستونزمن دي. برسېره پر دې، دا دقیق ارزښتونه لږ عملي غوښتنلیک لري ځکه چې په ماشین یا د محاسبې تمثیل کې کوم بدلون به پیچلتیا لږ څه توپیر ولري. برسېره پردې، د منابعو کارول د n د کوچنیو ارزښتونو لپاره مهم ندي، له همدې امله د پلي کولو اسانتیا اکثرا د کوچني n لپاره د ټیټ پیچلتیا په پرتله خورا زړه پورې وي.

د دې دلیلونو لپاره، ډیری پاملرنه د لوړ n لپاره د پیچلتیا چلند ته ورکول کیږي، دا دی، د n انفینیت ته د نږدې کیدو په صورت کې د هغې غیر سمپټوټیک چلند. د پایلې په توګه، لوی O نښې معمولا د پیچلتیا ښودلو لپاره کارول کیږي.

کمپیوټري موډلونه

د محاسبې ماډل انتخاب، کوم چې د اړینو عملیاتو مشخص کول چې د وخت په یو واحد کې ترسره کیږي، د پیچلتیا په ټاکلو کې مهم دی. دا ځینې وختونه د ملټي ټیپ ټورینګ ماشین په توګه راجع کیږي کله چې د محاسبې تمثیل په ځانګړي ډول بیان شوی نه وي.

د محاسبې ټاکونکی ماډل هغه دی چې په هغه کې د ماشین راتلونکي حالتونه او هغه عملیات چې ترسره کیږي په بشپړ ډول د پخواني حالت لخوا تعریف شوي. تکراري افعال، لامبدا کیلکولس، او د تورینګ ماشینونه لومړني ټاکونکي ماډلونه وو. د تصادفي لاسرسي ماشینونه (د RAM ماشینونو په نوم هم پیژندل کیږي) د ریښتیني نړۍ کمپیوټرونو سمولو لپاره مشهور تمثیل دی.

کله چې د محاسبې ماډل تعریف شوی نه وي، د ملټي ټیپ ټورینګ ماشین معمولا فرض کیږي. په ملټي ټیپ ټورینګ ماشینونو کې ، د وخت پیچلتیا د ډیری الګوریتمونو لپاره د RAM ماشینونو په څیر ورته ده ، سره له دې چې د دې انډول ترلاسه کولو لپاره په حافظه کې ډیټا څنګه ذخیره کیږي د پام وړ پاملرنې ته اړتیا وي.

د کمپیوټینګ په غیر متمرکز ماډل کې د محاسبې په ځینو مرحلو کې مختلف انتخابونه کیدی شي ، لکه د غیر متمرکز ټورینګ ماشینونه. د پیچلتیا په تیوري کې، ټول ممکنه اختیارونه په ورته وخت کې په پام کې نیول کیږي، او د غیر متمرکز وخت پیچلتیا هغه وخت ته اړتیا لري کله چې غوره انتخابونه تل ترسره کیږي. د دې لپاره چې په بل ډول یې واچوئ ، محاسبه په ورته وخت کې په ورته ډول ډیری ( ورته) پروسیسرونو باندې ترسره کیږي لکه څنګه چې اړتیا وي ، او د غیر ټاکلي محاسبې وخت هغه وخت دی چې د لومړي پروسیسر لخوا د محاسبې بشپړولو لپاره اخیستل کیږي. دا موازي په کوانټم کمپیوټینګ کې د سپرپوز شوي انټینګل حالتونو په کارولو سره کارول کیدی شي کله چې ځانګړي کوانټم الګوریتمونه چلوي ، لکه د مثال په توګه د شور د کوچني انټیجرونو فکتور کول.

حتی که د محاسبې دا ډول ماډل اوس مهال د عملي کیدو وړ نه وي، دا نظري اهمیت لري، په ځانګړې توګه د P = NP ستونزې سره تړاو لري، کوم چې پوښتنه کوي چې آیا د پیچلتیا ټولګي د "پولینومیال وخت" او "غیر ټاکلي پولی نومي وخت" په کارولو سره تولید شوي. حدود یو شان دي. په یو تعییناتي کمپیوټر کې، د NP-الګوریتم انډول کول "قطعي وخت" ته اړتیا لري. که چیرې یو کار په غیر متقابل سیسټم کې په پولینومیل وخت کې حل شي ، دا د NP مشکل طبقې پورې اړه لري. که یوه مسله په NP کې وي او د کومې بلې NP ستونزې څخه اسانه نه وي ، نو دا NP بشپړ ویل کیږي. د Knapsack ستونزه، د سفر پلورونکي ستونزه، او د بولین د رضایت ستونزه ټول د NP - بشپړ ترکیبي ستونزې دي. تر ټولو مشهور الګوریتم د دې ټولو ستونزو لپاره د پام وړ پیچلتیا لري. که چیرې د دې مسلو څخه کوم یو په ټاکلي ماشین کې په پولینومیل وخت کې حل شي، نو د NP ټولې ستونزې په پولینومیل وخت کې هم حل کیدی شي، او P = NP به تاسیس شي. تر 2017 پورې، دا په پراخه کچه انګیرل کیږي چې P NP، د دې معنی لري چې د NP ستونزې خورا خراب حالتونه په بنسټیز ډول حل کول ستونزمن دي، د بیلګې په توګه، د هرې ممکنه مودې (لسیزو) څخه ډیر وخت نیسي چې په زړه پورې معلوماتي اوږدوالی لري.

موازي او توزیع شوي کمپیوټري

موازي او توزیع شوي کمپیوټري په ډیری پروسیسرونو کې د پروسس ویشل شامل دي چې ټول په ورته وخت کې کار کوي. د مختلفو موډلونو ترمنځ بنسټیز توپیر د پروسیسرونو ترمنځ د معلوماتو لیږلو طریقه ده. د پروسیسرونو ترمنځ د ډیټا لیږد معمولا په موازي کمپیوټري کې خورا ګړندی وي ، پداسې حال کې چې په توزیع شوي کمپیوټر کې د پروسیسرونو ترمینځ د ډیټا لیږد په شبکه کې ترسره کیږي او پدې توګه د پام وړ ورو وي.

د N پروسیسرونو محاسبه لږترلږه د N لخوا د هغه وخت برخه اخلي چې دا یو واحد پروسیسر اخلي. په واقعیت کې، ځکه چې ځینې فرعي ټاسکونه موازي نه شي کیدی او ځینې پروسیسرونه ممکن د بل پروسیسر څخه پایلې ته انتظار ته اړتیا ولري، دا په نظرياتي توګه مثالی حد به هیڅکله ترلاسه نشي.

د پیچلتیا کلیدي مسله پدې توګه د الګوریتم رامینځته کول دي ترڅو د پروسیسرونو شمیر لخوا د کمپیوټري وخت محصول د امکان تر حده نږدې وي چې په یو واحد پروسیسر کې ورته محاسبه ترسره کولو لپاره اړین وي.

د کوانټم محاسبه

کوانټم کمپیوټر یو کمپیوټر دی چې د کوانټم میخانیک پر بنسټ د محاسبې ماډل لري. د کلیسا – ټورینګ مقاله د کوانټم کمپیوټرونو لپاره ریښتیا ده ، پدې معنی چې هره مسله چې د کوانټم کمپیوټر حل کولی شي د تورینګ ماشین لخوا هم حل کیدی شي. په هرصورت، ځینې دندې ممکن په تیوریکي توګه د کلاسیک کمپیوټر په ځای د کوانټم کمپیوټر په کارولو سره حل شي چې د پام وړ ټیټ لنډمهاله پیچلتیا سره. د اوس لپاره، دا په کلکه نظري ده، ځکه چې هیڅوک نه پوهیږي چې څنګه د عملي کوانټم کمپیوټر رامینځته کړي.

د کوانټم پیچلتیا تیوري د مختلف ډوله مسلو څیړلو لپاره رامینځته شوې چې د کوانټم کمپیوټرونو لخوا حل کیدی شي. دا د پوسټ کوانټم کریپټوګرافي کې کارول کیږي ، کوم چې د کریپټوګرافیک پروتوکولونو رامینځته کولو پروسه ده چې د کوانټم کمپیوټر بریدونو پروړاندې مقاومت لري.

د ستونزې پیچلتیا (ټیټ حدود)

د الګوریتمونو پیچلتیاوې چې ممکن ستونزه حل کړي، په شمول د ناڅرګند تخنیکونو په شمول، د ستونزې پیچلتیا ده. د پایلې په توګه، د ستونزې پیچلتیا د هر الګوریتم پیچلتیا سره مساوي ده چې دا حل کوي.

د پایلې په توګه، هر ډول پیچلتیا چې په لوی O نوټیشن کې ورکړل شوي د الګوریتم او ورسره تړلې ستونزې دواړه پیچلتیا څرګندوي.

له بلې خوا، د مسلې په پیچلتیا کې د غیر معمولي ټیټ حدونو ترلاسه کول ډیری وختونه ستونزمن وي، او د دې کولو لپاره لږې ستراتیژۍ شتون لري.

د ډیری مسلو د حل کولو لپاره، ټول داخل شوي معلومات باید ولوستل شي، کوم چې د معلوماتو شدت سره متناسب وخت نیسي. د پایلې په توګه، دا ډول ستونزې لږترلږه خطي پیچلتیا لري، یا په لوی اومیګا نوټیشن کې، د Ω (n) پیچلتیا.

ځینې ​​ستونزې، لکه د کمپیوټر الجبرا او کمپیوټري الجبریک جیومیټري کې، خورا لوی حلونه لري. ځکه چې محصول باید لیکل شي، پیچلتیا د محصول اعظمي اندازې لخوا محدوده ده.

د ترتیب کولو الګوریتم لپاره اړین پرتله کولو شمیره د Ω (nlogn) غیر خطي ټیټ حد لري. د پایلې په توګه، د غوره ترتیب کولو الګوریتم خورا اغیزمن دي ځکه چې د دوی پیچلتیا O (nlogn) ده. حقیقت دا دی چې ن شتون لري! د شیانو د تنظیم کولو لارې د دې ټیټ حد ته رسوي. ځکه چې هر پرتله کول د n دا ټولګه تقسیموي! امرونه په دوه برخو ویشئ، د ټولو امرونو د توپیر لپاره د N پرتله کولو شمیر باید 2N > n! وي، د سټرلینګ فارمول لخوا د O(nlogn) معنی لري.

د یوې ستونزې بلې ستونزې ته کمول د پیچلتیا کمولو محدودیتونو ترلاسه کولو لپاره یوه عامه تګلاره ده.

د الګوریتم پراختیا

د الګوریتم پیچلتیا ارزونه د ډیزاین پروسې یو مهم عنصر دی ځکه چې دا د هغه فعالیت په اړه ګټور معلومات چمتو کوي چې تمه کیدی شي.

دا یو پرله پسې غلط فهمۍ دی چې د مور د قانون په پایله کې، کوم چې د عصري کمپیوټر ځواک د پراخې ودې وړاندوینه کوي، د الګوریتم پیچلتیا ارزونه به لږ اړونده شي. دا غلط دی ځکه چې د بریښنا زیاتوالی د ډیرو ډیټا (لوی ډاټا) پروسس کولو ته اجازه ورکوي. د مثال په توګه، هر الګوریتم باید د یوې ثانیې څخه لږ وخت کې ښه کار وکړي کله چې د الفبا په ترتیب سره د څو سلګونو ننوتلو لیست ترتیب کړي، لکه د کتاب کتابتون. له بلې خوا، د یو ملیون ننوتلو لپاره (د مثال په توګه، د لوی ښار د تلیفون شمیرې)، لومړني الګوریتمونه چې د O(n2) پرتله کولو ته اړتیا لري باید یو ټریلیون پرتله کړي، چې د 10 په سرعت کې به درې ساعته وخت ونیسي. په هره ثانیه کې ملیونونه پرتله کول. Quicksort او ضم کولو ترتیب، له بلې خوا، یوازې د nlogn پرتله کولو ته اړتیا لري (د پخوانیو لپاره د اوسط قضیې پیچلتیا په توګه، د وروستي لپاره د بدترین قضیې پیچلتیا په توګه). دا د n = 30,000,000 لپاره شاوخوا 1,000,000 پرتله کوي، کوم چې په هره ثانیه کې د 3 ملیون پرتله کولو لپاره یوازې 10 ثانیې وخت نیسي.

د پایلې په توګه، د پیچلتیا ارزونه ممکن د پلي کولو دمخه د ډیری غیر موثر الګوریتمونو له مینځه وړو لپاره اجازه ورکړي. دا د پیچلو الګوریتمونو ښه کولو لپاره هم کارول کیدی شي پرته لدې چې ټول احتمالي ډولونه ازموي. د پیچلتیا مطالعه اجازه ورکوي چې د پیچلي الګوریتم خورا قیمتي مرحلو په ټاکلو سره د پلي کولو موثریت زیاتولو لپاره هڅې تمرکز وکړي.