Асновы тэорыі складанасці вылічэнняў 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-машыны) з'яўляюцца папулярнай парадыгмай для мадэлявання рэальных кампутараў.

Калі мадэль вылічэнняў не вызначана, звычайна мяркуецца шматстужковая машына Цьюрынга. На шматстужковых машынах Цьюрынга часовая складанасць такая ж, як і на машынах з аператыўнай памяці для большасці алгарытмаў, хоць для дасягнення гэтай эквівалентнасці можа спатрэбіцца значная ўвага да таго, як дадзеныя захоўваюцца ў памяці.

Розныя выбары могуць быць зроблены на некаторых этапах вылічэнняў у недэтэрмінаванай мадэлі вылічэнняў, напрыклад, у недэтэрмінаваных машынах Цьюрынга. У тэорыі складанасці ўсе магчымыя варыянты разглядаюцца адначасова, а недэтэрмінаваная часовая складанасць - гэта колькасць часу, неабходнага, калі заўсёды робяцца лепшыя выбары. Іншымі словамі, вылічэнні выконваюцца адначасова на столькіх (ідэнтычных) працэсарах, колькі патрабуецца, а недэтэрмінаваны час вылічэнняў - гэта час, затрачаны першым працэсарам на завяршэнне вылічэнняў. Гэты паралелізм можа быць выкарыстаны ў квантавых вылічэннях з дапамогай накладзеных пераблытаных станаў пры запуску спецыялізаваных квантавых алгарытмаў, такіх як, напрыклад, разкладанне дробных цэлых лікаў Шора на множнікі.

Нават калі такая мадэль вылічэнняў у цяперашні час невыканальная, яна мае тэарэтычнае значэнне, асабліва ў дачыненні да праблемы P = NP, у якой задаецца пытанне, ці класы складанасці, атрыманыя з выкарыстаннем «паліномнага часу» і «недэтэрмінаванага паліномнага часу» ў якасці найменшага верхняга межы аднолькавыя. На дэтэрмінаваным кампутары мадэляванне NP-алгарытму патрабуе «экспанентнага часу». Калі задача можа быць вырашана за паліномны час у недэтэрмінаванай сістэме, яна належыць да класа складанасці NP. Калі праблема знаходзіцца ў NP і не прасцей, чым любая іншая задача NP, яна называецца NP-поўнай. Задача Ранца, задача камаўнічага і задача булева выканальнасці - усё гэта NP-поўныя камбінаторныя задачы. Найбольш вядомы алгарытм мае экспанентную складанасць для ўсіх гэтых задач. Калі любую з гэтых задач можна было б вырашыць за паліномны час на дэтэрмінаванай машыне, то ўсе задачы NP таксама можна было б вырашыць за паліномны час, і P = NP было б усталявана. Па стане на 2017 год шырока прынята лічыць, што P NP, маючы на ​​ўвазе, што горшыя сітуацыі з праблемамі NP прынцыпова цяжкія для вырашэння, г.зн. займаюць значна больш часу, чым любы магчымы прамежак часу (дзесяцігоддзяў), улічваючы цікавыя даўжыні ўваходных дадзеных.

Паралельныя і размеркаваныя вылічэнні

Паралельныя і размеркаваныя вылічэнні ўключаюць дзяленне апрацоўкі на некалькі працэсараў, якія працуюць адначасова. Прынцыповым адрозненнем паміж рознымі мадэлямі з'яўляецца метад перадачы дадзеных паміж працэсарамі. Перадача даных паміж працэсарамі, як правіла, вельмі хуткая пры паралельных вылічэннях, у той час як перадача даных паміж працэсарамі ў размеркаваных вылічэннях ажыццяўляецца па сетцы і, такім чынам, істотна павольней.

Вылічэнне на N працэсарах займае, па меншай меры, частку N часу, якое займае адзін працэсар. На самай справе, паколькі некаторыя падзадачы не могуць быць паралелізаваны, а некаторым працэсарам, магчыма, прыйдзецца чакаць выніку ад іншага працэсара, гэта тэарэтычна ідэальнае абмежаванне ніколі не будзе дасягнута.

Такім чынам, ключавая праблема складанасці заключаецца ў распрацоўцы алгарытмаў, каб здабытак часу вылічэнняў на колькасць працэсараў быў як мага бліжэй да часу, неабходнага для выканання таго ж вылічэння на адным працэсары.

Квантавыя вылічэнні

Квантавы камп’ютар — гэта камп’ютар з мадэллю вылічэнняў, заснаванай на квантавай механіцы. Тэзіс Чэрча-Цьюрынга верны для квантавых кампутараў, маючы на ​​ўвазе, што любая праблема, якую можа вырашыць квантавы кампутар, таксама можа быць вырашана машынай Цьюрынга. Аднак некаторыя задачы тэарэтычна могуць быць вырашаны з дапамогай квантавага кампутара, а не класічнага кампутара са значна меншай часовай складанасцю. Пакуль што гэта строга тэарэтычна, бо ніхто не ведае, як распрацаваць практычны квантавы кампутар.

Квантавая тэорыя складанасці была створана для даследавання розных тыпаў праблем, якія могуць быць вырашаны квантавымі кампутарамі. Ён выкарыстоўваецца ў постквантавай крыптаграфіі, якая ўяўляе сабой працэс стварэння крыптаграфічных пратаколаў, устойлівых да квантавых кампутарных нападаў.

Складанасць задачы (ніжнія межы)

Невялікая колькасць складанасці алгарытмаў, якія могуць вырашыць праблему, у тым ліку нераскрытых метадаў, - гэта складанасць задачы. У выніку складанасць задачы роўная складанасці любога алгарытму, які яе вырашае.

У выніку любая складанасць, зададзеная ў вялікім абазначэнні O, уяўляе складанасць як алгарытму, так і спадарожнай задачы.

З іншага боку, атрымаць нетрывіяльныя ніжнія межы складанасці пытання часта бывае складана, і для гэтага існуе некалькі стратэгій.

Для таго, каб вырашыць большасць праблем, усе ўваходныя даныя павінны быць прачытаны, што займае час, прапарцыйнае велічыні дадзеных. У выніку такія задачы маюць прынамсі лінейную складанасць, або, у вялікіх амегах, складанасць Ω(n).

Некаторыя задачы, напрыклад, па кампутарнай алгебры і вылічальнай алгебраічнай геаметрыі, маюць вельмі вялікія рашэнні. Паколькі вывад павінен быць запісаны, складанасць абмяжоўваецца максімальным памерам вываду.

Колькасць параўнанняў, неабходных для алгарытму сартавання, мае нелінейную ніжнюю мяжу Ω(nlogn). У выніку лепшыя алгарытмы сартавання з'яўляюцца найбольш эфектыўнымі, паколькі іх складанасць складае O(nlogn). Справа ў тым, што ёсць п! спосабаў арганізацыі п рэчаў прыводзіць да гэтай ніжняй мяжы. Таму што кожнае параўнанне падзяляе гэты збор н! замовы на дзве часткі, колькасць N параўнанняў, неабходных для адрознення ўсіх парадкаў, павінна быць 2N > n!, што азначае O(nlogn) па формуле Стырлінга.

Звядзенне праблемы да іншай - гэта звычайная стратэгія атрымання абмежаванняў меншай складанасці.

Распрацоўка алгарытму

Ацэнка складанасці алгарытму з'яўляецца важным элементам працэсу праектавання, паколькі дае карысную інфармацыю аб прадукцыйнасці, якую можна чакаць.

Частае неразуменне, што ў выніку дзеяння закона Мура, які прадказвае экспанентны рост магутнасці сучасных кампутараў, ацэнка складанасці алгарытмаў стане менш актуальнай. Гэта няправільна, таму што падвышаная магутнасць дазваляе апрацоўваць вялізныя аб'ёмы даных (вялікія дадзеныя). Напрыклад, любы алгарытм павінен добра працаваць менш чым за секунду пры сартаванні ў алфавітным парадку спісу з некалькіх сотняў запісаў, напрыклад, бібліяграфіі кнігі. З іншага боку, для мільёна запісаў (напрыклад, тэлефонных нумароў вялікага горада) асноўныя алгарытмы, якія патрабуюць параўнання O(n2), павінны былі б выканаць трыльён параўнанняў, што заняло б тры гадзіны пры хуткасці 10 мільён параўнанняў у секунду. Хуткая сартаванне і сартаванне зліццём, з іншага боку, патрабуюць толькі параўнанняў nlogn (як сярэдняя складанасць для першага, як складанасць у горшым выпадку для апошняга). Гэта вырабляе каля 30,000,000 1,000,000 3 параўнанняў для n = 10 XNUMX XNUMX, што зойме ўсяго XNUMX секунды пры XNUMX мільёнах параўнанняў у секунду.

У выніку, ацэнка складанасці можа дазволіць ліквідаваць мноства неэфектыўных алгарытмаў да ўкаранення. Гэта таксама можна выкарыстоўваць для тонкай налады складаных алгарытмаў без неабходнасці правяраць усе магчымыя варыянты. Вывучэнне складанасці дазваляе сканцэнтраваць намаганні на павышэнні эфектыўнасці рэалізацыі шляхам вызначэння найбольш затратных крокаў складанага алгарытму.