Кіріспе

Алгоритмді орындау үшін кеткен уақытты бағалау

Теориялық компьютерлік ғылымда уақыт күрделілігі – алгоритмді орындау үшін компьютерге қажетті уақытты сипаттайтын есептеу күрделілігі. Уақыт күрделілігі әдетте алгоритм орындаған элементарлық операциялардың санын есептеу арқылы бағаланады, әрбір элементарлық операцияны орындау үшін белгілі бір уақыт қажет деп ескереді. Осылайша, кеткен уақыт мөлшері мен алгоритм орындаған элементарлық операциялардың саны тұрақты коэффициентпен байланысты деп есептеледі. Алгоритмнің жұмыс істеу уақыты бірдей мөлшердегі әртүрлі кірістерге қарай өзгеруі мүмкін болғандықтан, көбінесе ең нашар жағдайдың уақыт күрделілігі қарастырылады, ол берілген мөлшердегі кіріс үшін қажетті ең көп уақытты көрсетеді. Орташа жағдай күрделілігі де бар, бірақ ол көбінесе нақты көрсетіледі, ол берілген мөлшердегі кірістердегі уақыттың орташа мәнін білдіреді (бұл мағыналы, өйткені берілген мөлшердегі кірістердің саны шекті). Екі жағдайда да уақыт күрделілігі әдетте кіріс мөлшерінің функциясы ретінде беріледі.

| Логарифмдік уақыт | DLOGTIME | n | Екілік іздеу |
|---|---|---|---|
| Полилогарифмдік уақыт | | | |
| Бөлшектік қуат | | n | kd-ағаштағы диапазондық іздеу |
| Сызықтық уақыт | | n | Сұрыпталмаған массивтегі ең кіші немесе ең үлкен элементті табу. Кадане алгоритмі. Сызықтық іздеу |
| "n log*n" уақыт | | | Seidel көпбұрышты үшбұрыштау алгоритмі |
| Сызықтық-логарифмдік уақыт | | n log n | Ең жылдам салыстыру сұрыптауы. Жылдам Фурье түрлендіргіші |
| Квазисызықтық уақыт | | | Көпнүктелі полиномдық бағалау |
| Квадраттық уақыт | | n² | Көпіршік сұрыптау, енгізу сұрыптау, тікелей конволюция |
| Кубтық уақыт | | n³ | Екі матрицаны тікелей көбейту. Ішінара корреляцияны есептеу |
| Полиномдық уақыт | P | | Линейлік бағдарламалау үшін Кармакер алгоритмі. AKS жай сан тесті |
| Квазиполиномдық уақыт | QP | | Бағытталған Штейнер ағашының жақсы жуықтама алгоритмі, жақсы парность ойыны шешімі, жақсы граф изоморфизмі алгоритмі |
| Субэкспоненциалдық уақыт (бірінші анықтама) | SUBEXP | | Барлық үшін , MA-ға тең болмаса EXPTIME (төменде қараңыз). Графты толық динамикалық түрде жазық деп анықтауға болады, енгізу/жою операциясына жұмсалатын уақыт бойынша. |

Сызықтық уақыт

Алгоритмнің сызықтық уақыт немесе O(n) уақыт алатыны айтылады, егер оның уақыт күрделілігі O(n) болса. Бұл, негізінен, алгоритмнің жұмыс істеу уақыты кіріс мөлшерімен бірге сызықтық түрде өседі дегенді білдіреді. Нақтырақ айтқанда, бұл дегеніміз, кез келген n мөлшеріндегі кіріс үшін жұмыс істеу уақыты c тұрақтысына тең немесе одан кем болады. Мысалы, тізімнің барлық элементтерін қосатын процедура, егер қосу уақыты тұрақты болса немесе кем дегенде тұрақтымен шектелсе, тізімнің ұзындығына пропорционалды уақытты қажет етеді. Алгоритм өзінің барлық кіріс деректерін бірінен соң бірін оқып отыратын жағдайларда сызықтық уақыт – ең жақсы мүмкін уақыт күрделілігі. Сондықтан, сызықтық немесе кемінде жақындаған сызықтық уақытты көрсететін алгоритмдерді табуға көп зерттеулер жұмсалды. Бұл зерттеулер бағдарламалық және аппараттық әдістерді қамтиды. Параллелизмді пайдаланып осыны қамтамасыз ететін бірнеше аппараттық технологиялар бар. Мысалы, мазмұндық адрестік жад. Сызықтық уақыт тұжырымы, Boyer-Moore жол іздеу алгоритмі және Ukkonen алгоритмі сияқты жол сәйкестендіру алгоритмдерінде қолданылады.

Квадраттан төмен уақыт

Алгоритм субквадраттық уақытта жұмыс істейді деп айтылады, егер
Мысалы, қарапайым, салыстыру негізінде жұмыс істейтін сұрыптау алгоритмдері квадраттық болады (мысалы, енгізу сұрыптау), бірақ одан да жетілдірілген алгоритмдер субквадраттық уақытта жұмыс істей алады (мысалы, қабықша сұрыптау). Кез келген мақсаттағы сұрыптау алгоритмдері сызықтық уақытта жұмыс істемейді, бірақ квадраттық уақыттан субквадраттық уақытқа өту өте маңызды.

Суперполиномдық уақыт

Егер T(n) ешқандай полиноммен жоғарыдан шектелмесе, онда алгоритм суперполиномиалдық уақытты қажет етеді деп айқындалады. Кішкентай омега нотациясын пайдалану арқылы, ол барлық тұрақты c үшін ω(nc) уақытты құрайды, мұнда n – кіріс параметрі, әдетте кірістегі биттер саны. Мысалы, n өлшемді кірісте 2n қадаммен орындалатын алгоритмге суперполиномиалдық уақыт (нақтырақ айтқанда, экспоненциалдық уақыт) қажет. Экспоненциалдық ресурстарды қолданатын алгоритм әрине суперполиномиалды болып табылады, бірақ кейбір алгоритмдер өте әлсіз суперполиномиалды ғана болады. Мысалы, Адлеман–Померанс–Рюмелидің сандық тесті n биттік кірісте nO(log log n) уақытында жұмыс істейді; бұл жеткілікті үлкен n үшін кез келген полиномнан жылдам өседі, бірақ кіріс мөлшері кішкентай дәрежелі полиноммен басып озудан бұрын өте үлкен болуы керек. Суперполиномиалдық уақытты қажет ететін алгоритм күрделілік класы P-ден тысқары орналасады. Кобхамның тезисі мұндай алгоритмдердің практикалық еместігін жобалайды, және көп жағдайда олар сондай болады. P және NP мәселесі шешілмегендіктен, NP-толық мәселелеріне суперполиномиалдық уақыт қажеттігі белгісіз.

Квазиполиномдық уақыт

Квазиполиномиалдық уақыт алгоритмдері – жұмыс істеу уақыты квазиполиномиалдық өсімді көрсететін алгоритмдер, бұл мінез-құлық полиномиалдық уақыттан баяу болуы мүмкін, бірақ экспоненциалдық уақыттан әлдеқайда жылдам. Квазиполиномиалдық уақыт алгоритмінің нашар жағдайдағы жұмыс істеу уақыты – бұл кейбір тұрақты мән үшін . Егер онда полиномиалдық уақытқа, ал егер онда сублинейлік уақытқа ие болады. Бізге квазиполиномиалдық уақыт алгоритмі бар, бірақ полиномиалдық уақыт алгоритмі белгілі емес кейбір мәселелер бар. Мұндай мәселелер жуықтау алгоритмдерінде туындайды; әйгілі мысал – бағытталған Штайнер ағашы мәселесі, онда (n – төбелер саны) жуықтау коэффициентіне қол жеткізетін квазиполиномиалдық уақытты жуықтау алгоритмі бар, бірақ мұндай полиномиалдық уақыт алгоритмінің бар екенін көрсету ашық мәселе болып қалады. Квазиполиномиалдық уақыт шешімі бар, бірақ полиномиалдық уақыт шешімі жоқ басқа есептеу мәселелеріне отырғызылған клика мәселесі кіреді, онда мақсат – клика мен кездейсоқ графтың бірігімінде үлкен кликаны табу. Квазиполиномиалдық түрде шешілгенімен, отырғызылған клика мәселесінің полиномиалдық уақыт шешімі жоқ деп болжанады; бұл отырғызылған клика болжамы есептеу ойындарының теориясында, қасиеттерді тексеруде және машиналық оқытуда бірнеше басқа мәселелердің қиындығын дәлелдеу үшін есептеулік қиындығының болжамы ретінде қолданылды. QP күрделілік класы квазиполиномиалдық уақыт алгоритмдері бар барлық мәселелерден тұрады. Оны DTIME арқылы келесідей анықтауға болады.

NP-толық проблемалармен байланысы

Күрделілік теориясында P және NP арасындағы шешілмеген мәселе, NP-дегі барлық проблемалардың полиномиалдық уақытта шешілетін алгоритмі бар ма, деген сұрақ туындайды. NP-толық проблемаларына арналған барлық белгілі ең жақсы алгоритмдер, мысалы 3SAT сияқты, экспоненциалды уақытты қажет етеді. Шындығында, көптеген табиғи NP-толық проблемалары үшін олардың экспоненциалды емес уақытта шешілетін алгоритмдері жоқ деп болжанады. Мұнда "экспоненциалды емес уақыт" төменде келтірілген екінші анықтамамен түсіндіріледі. (Дегенмен, жақындық матрицалары арқылы табиғи түрде бейнеленген көптеген графиктердің проблемалары кіріс мөлшері төбелер санының квадратына тең болғандықтан, экспоненциалды емес уақытта шешіледі.) Бұл болжам (k SAT проблемасы үшін) экспоненциалды уақыт гипотезасы деп аталады. NP-толық проблемаларында квазиполиномиалдық уақытта шешілетін алгоритмдер жоқ деп болжанғандықтан, жуықтау алгоритмдері саласындағы кейбір нәтижелер NP-толық проблемаларында квазиполиномиалдық уақытта шешілетін алгоритмдер жоқ деп қарастырады. Мысалы, жиын жабу проблемасы үшін белгілі жуықтау мүмкін емес нәтижелерді қараңыз.

Субэкспоненциалдық уақыт

Субэкспоненциалдық уақыт термині кейбір алгоритмдердің жұмыс істеу уақыты кез келген полиномнан жылдам өсіп, бірақ экспоненциалдықтан әлдеқайда кіші болатынын көрсету үшін қолданылады. Осыған орай, субэкспоненциалдық уақыт алгоритмдері бар мәселелер, тек экспоненциалдық алгоритмдері бар мәселелерге қарағанда шешуге біршама оңайырақ болады. "Субэкспоненциалдық" ұғымының нақты анықтамасы туралы жалпы келісім жоқ, бірақ ең көп қолданылатыны екеуі төменде берілген.

Бірінші анықтама

Мәселе субекспоненциалды уақытта шешілетін болады, егер оны шешуге кететін уақыттың логарифмі кез келген берілген полиномнан кішірек болса. Нақтырақ айтқанда, мәселе субекспоненциалды уақытта болады, егер кез келген ε > 0 үшін O(2<sup>nε</sup>) уақытында оны шешетін алгоритм болса. Мұндай мәселелердің барлық жиынтығы SUBEXP күрделілік класын құрайды, оны DTIME арқылы былай анықтауға болады. Субекспоненциалдық тұжырымы ε-ға қатысты біркелкі емес, себебі ε кірістің бір бөлігі емес және әр ε үшін мәселені шешуге арналған жеке алгоритм болуы мүмкін.

Екінші анықтама

Кейбір авторлар субэкспоненциалдық уақытты орындалу уақыттары деп анықтайды. Бұл анықтама субэкспоненциалдық уақыттың алғашқы анықтамасына қарағанда үлкен орындалу уақыттарына мүмкіндік береді. Мұндай субэкспоненциалдық уақыт алгоритмінің мысалы – бүтін сандарды факторлаудың ең белгілі классикалық алгоритмі, жалпы сандық өріс ілгісі, ол кірістің ұзындығы n болғанда шамамен уақытта жұмыс істейді. Тағы бір мысал – 1982 жылдан 2016 жылға дейін ең жақсы белгілі алгоритм шешкен граф изоморфизмі мәселесі. Алайда, STOC 2016 конференциясында квазиполиномиалдық уақыт алгоритмі ұсынылды. Алгоритмге мысалдың мөлшері, төбелер саны немесе қабырғалар саны бойынша субэкспоненциалды болуға рұқсат етудің маңызы бар. Параметрленген күрделілікте бұл айырмашылық шешімдердің проблемалары мен k параметрлерінің жұптарын қарастыру арқылы нақты көрінеді. SUBEPT – k бойынша субэкспоненциалдық және кірістің мөлшері n бойынша полиномиалдық уақытта жұмыс істейтін барлық параметрленген проблемалардың класы: Нақтырақ айтқанда, SUBEPT – L мәселесін уақытында шешетін алгоритммен есептелетін функция бар барлық параметрленген проблемалардың класы.

Экспоненциалдық уақыт гипотезасы

Экспоненциалдық уақыт гипотезасы (ЭУГ) – 3SAT, конъюнктивті қалыпты формадағы, әрбір клаузада ең көп үш литераль және n айнымалысы бар Буль формулаларының қанағаттандырылатындығы мәселесі, 2o(n) уақытында шешілмейді. Нақтырақ айтқанда, гипотеза бойынша, 2cn уақытында ешқандай детерминистік Тьюринг машинасымен 3SAT-ты шеше алмайтын абсолютті тұрақты c > 0 бар. m – клаузалар санын білдіретін болса, ЭУГ, кез келген k ≥ 3 бүтін саны үшін kSAT-ты 2o(m) уақытында шеше алмайтын гипотезаға тең. Экспоненциалдық уақыт гипотезасы P ≠ NP екенін білдіреді.

Экспоненциалдық уақыт

Алгоритмнің жұмыс уақыты T(n) 2poly(n) арқылы жоғары шектелген болса, онда ол экспоненциалды уақытты алгоритм деп аталады, мұнда poly(n) – n-ге қатысты кез келген полином. Нақтырақ айтқанда, егер T(n) белгілі бір тұрақты k үшін O(2nk) арқылы шектелген болса, алгоритм экспоненциалды уақытты болып табылады. Детерминистік Тьюринг машинасының экспоненциалды уақытты алгоритмдерін шешетін мәселелер EXP деп аталатын күрделілік класын құрайды. Кейде экспоненциалды уақыт T(n) = 2O(n) тең болатын алгоритмдерді көрсету үшін қолданылады, мұнда көрсеткіш n-нің сызықтық функциясынан аспайды. Бұл E күрделілік класын тудырады.

Факторлық уақыт

Егер T(n) функциясы n! факторлық функциясымен жоғары шектелген болса, онда алгоритм факторлық уақытты алгоритм деп аталады. Факторлық уақыт экспоненциалдық уақыттың (EXP) ішкі жиыны болып табылады, себебі барлық жағдайларда. Дегенмен, ол E-нің ішкі жиыны емес.

Факторлық уақытта жұмыс істейтін алгоритмнің мысалы – бұл сынақ және қате әдісіне негізделген, өте тиімсіз сұрыптау алгоритмі болып табылатын bogosort. Bogosort n элементтен тұратын тізімді, тізімді реттелген күйге келгенше қайта-қайта шатастыру арқылы сұрыптайды. Орташа жағдайда, bogosort алгоритмінің әрбір итерациясы n элементтің n! мүмкін орналасуының біреуін тексереді. Егер элементтер әртүрлі болса, тек бір ғана орналасу реттелген болады. Bogosort шексіз маймыл теоремасымен туыстық байланысқа ие.