ЕИТЦ/ИС/ЦЦТФ Основе теорије сложености рачунара

Пошто количина ресурса потребних за покретање алгоритма варира у зависности од величине улаза, сложеност се обично изражава као функција ф(н), где је н величина улаза, а ф(н) је или сложеност у најгорем случају ( максималну количину потребних ресурса за све улазе величине н) или просечну сложеност случаја (просек количине ресурса за све улазе величине н). Број потребних елементарних операција на улазу величине н обично се наводи као временска сложеност, где се верује да елементарне операције трају константно време на одређеном рачунару и да се мењају само за константан фактор када се покрећу на другој машини. Количина меморије коју алгоритам захтева на улазу величине н позната је као комплексност простора.

Време је ресурс који се најчешће сматра. Када се израз „сложеност“ користи без квалификатора, обично се односи на сложеност времена.

Традиционалне јединице времена (секунде, минуте и тако даље) се не користе у теорији сложености јер се превише ослањају на изабрани рачунар и напредак технологије. На пример, рачунар данас може да изврши алгоритам знатно брже од рачунара из 1960-их, али то је због технолошких открића у рачунарском хардверу, а не због инхерентног квалитета алгоритма. Циљ теорије сложености је да квантификује инхерентне временске потребе алгоритама, или фундаментална временска ограничења која би алгоритам наметнуо било ком рачунару. Ово се постиже пребројавањем колико се основних операција изводи током израчунавања. Ове процедуре се обично називају корацима јер се сматра да трају константно време на одређеној машини (тј. на њих не утиче количина улаза).

Други кључни ресурс је количина рачунарске меморије која је потребна за извођење алгоритама.

Други често коришћени ресурс је количина аритметичких операција. У овом сценарију се користи термин „аритметичка сложеност“. Временска сложеност је генерално производ аритметичке сложености са константним фактором ако је познато горње ограничење на величину бинарне репрезентације бројева који се јављају током израчунавања.

Величина целих бројева који се користе током израчунавања није ограничена за многе методе и нереално је претпоставити да је за аритметичке операције потребно одређено време. Као резултат, временска сложеност, такође позната као сложеност бита, може бити знатно већа од аритметичке сложености. Аритметичка потешкоћа израчунавања детерминанте нн целобројне матрице, на пример, је О(н^3) за стандардне технике (Гаусова елиминација). Пошто се величина коефицијената може експоненцијално проширити током израчунавања, сложеност бита истих метода је експоненцијална у н. Ако се ове технике користе заједно са мултимодуларном аритметиком, сложеност бита се може смањити на О(н^4).

Сложеност бита, формално гледано, односи се на број операција над битовима потребних за покретање алгоритма. Она је једнака временској сложености до константног фактора у већини рачунских парадигми. Број операција над машинским речима које захтевају рачунари пропорционалан је сложености бита. За реалистичне моделе прорачуна, временска сложеност и сложеност бита су стога идентични.

Ресурс који се често узима у обзир при сортирању и претраживању је количина поређења уноса. Ако су подаци добро распоређени, ово је добар показатељ временске сложености.

На свим потенцијалним улазима, бројање корака у алгоритму је немогуће. Пошто сложеност улаза расте са његовом величином, он се обично представља као функција величине улаза н (у битовима), тако да је сложеност функција од н. Међутим, за улазе исте величине, сложеност алгоритма може значајно да варира. Као резултат тога, рутински се користе различите функције сложености.

Сложеност најгорег случаја је збир све сложености за све улазе величине н, док је сложеност просечног случаја збир све сложености за све улазе величине н (ово има смисла, пошто је број могућих улаза дате величине коначан). Када се термин „сложеност“ користи без даљег дефинисања, узима се у обзир временска сложеност у најгорем случају.

Познато је да је сложеност најгорег и просечног случаја тешко правилно израчунати. Штавише, ове тачне вредности имају мало практичне примене јер би свака промена у машинској или прорачунској парадигми мало променила сложеност. Штавише, коришћење ресурса није пресудно за мале вредности н, стога је лакоћа имплементације често привлачнија од ниске сложености за мало н.

Из ових разлога, највише пажње се посвећује понашању сложености за велико н, односно његовом асимптотичком понашању када се н приближава бесконачности. Као резултат тога, велика О нотација се обично користи за означавање сложености.

Рачунски модели

Одабир прорачунског модела, који се састоји од специфицирања битних операција које се изводе у јединици времена, кључан је у одређивању сложености. Ово се понекад назива Тјуринг машина са више трака када парадигма рачунања није посебно описана.

Детерминистички модел прорачуна је онај у коме су наредна стања машине и операције које треба да се изврше у потпуности дефинисане претходним стањем. Рекурзивне функције, ламбда рачун и Тјурингове машине су били први детерминистички модели. Машине са случајним приступом (познате и као РАМ машине) су популарна парадигма за симулацију рачунара у стварном свету.

Када рачунски модел није дефинисан, обично се претпоставља Тјурингова машина са више трака. На Тјуринговим машинама са више трака, временска сложеност је иста као на РАМ машинама за већину алгоритама, иако је потребна значајна пажња у начину на који се подаци чувају у меморији да би се постигла ова еквиваленција.

Могу се направити различити избори у неким корацима прорачуна у недетерминистичком моделу рачунарства, као што су недетерминистичке Тјурингове машине. У теорији сложености, све изводљиве опције се разматрају у исто време, а недетерминистичка временска сложеност је количина времена која је потребна када се увек доносе најбољи избори. Другим речима, израчунавање се врши истовремено на онолико (идентичних) процесора колико је потребно, а недетерминистичко време израчунавања је време потребно првом процесору да заврши прорачун. Овај паралелизам се може користити у квантном рачунарству коришћењем суперпонираних заплетених стања при покретању специјализованих квантних алгоритама, као што је Шорова факторизација ситних целих бројева, на пример.

Чак и ако такав модел прорачуна тренутно није изводљив, он има теоријски значај, посебно у вези са П = НП проблемом, који поставља питање да ли су класе сложености произведене коришћењем „полиномског времена“ и „недетерминистичког полиномског времена“ као најмање горње границе су исте. На детерминистичком рачунару, симулација НП-алгоритма захтева „експоненцијално време“. Ако се задатак може решити у полиномском времену на недетерминистичком систему, он припада НП класи тежине. Ако је проблем у НП и није лакши од било ког другог НП проблема, каже се да је НП-потпун. Проблем ранца, проблем трговачког путника и Булов проблем задовољивости су НП-потпуни комбинаторни проблеми. Најпознатији алгоритам има експоненцијалну сложеност за све ове проблеме. Ако би се било који од ових проблема могао решити у полиномском времену на детерминистичкој машини, онда би се сви НП проблеми могли решити и у полиномском времену, и П = НП би се установило. Од 2017. године, широко се претпоставља да је П НП, што имплицира да је најгоре ситуације НП проблема фундаментално тешко решити, тј. да им је потребно много дуже од било ког изводљивог временског распона (деценијама) с обзиром на занимљиве улазне дужине.

Паралелно и дистрибуирано рачунарство

Паралелно и дистрибуирано рачунарство укључује поделу обраде на више процесора који сви раде у исто време. Основна разлика између различитих модела је начин слања података између процесора. Пренос података између процесора је обично веома брз у паралелном рачунарству, док се пренос података између процесора у дистрибуираном рачунарству обавља преко мреже и стога је знатно спорији.

Прорачун на Н процесора узима најмање количник са Н времена потребног једном процесору. У стварности, пошто се неки подзадаци не могу паралелизирати и неки процесори ће можда морати да чекају резултат од другог процесора, ова теоретски идеална граница никада неће бити постигнута.

Кључно питање сложености је стога развити алгоритме тако да производ времена рачунања на број процесора буде што је могуће ближи времену потребном за обављање истог прорачуна на једном процесору.

Квантно рачунање

Квантни рачунар је рачунар са рачунским моделом заснованим на квантној механици. Черч-Тјурингова теза важи за квантне рачунаре, што имплицира да било који проблем који квантни рачунар може да реши може такође бити решен Тјуринговом машином. Међутим, неки задаци би се теоретски могли решити коришћењем квантног рачунара, а не класичног рачунара са знатно нижом временском сложеношћу. За сада, ово је строго теоретски, јер нико не зна како да развије практичан квантни рачунар.

Квантна теорија сложености је створена да истражи различите врсте проблема које могу да реше квантни рачунари. Користи се у пост-квантној криптографији, што је процес стварања криптографских протокола који су отпорни на квантне компјутерске нападе.

Сложеност проблема (доње границе)

Најнижи део сложености алгоритама који могу да реше проблем, укључујући неоткривене технике, је сложеност проблема. Као резултат тога, сложеност проблема је једнака сложености било ког алгоритма који га решава.

Као резултат, свака сложеност дата у великој О нотацији представља сложеност и алгоритма и пратећег проблема.

С друге стране, добијање нетривијалних доњих граница сложености питања је често тешко, а постоји неколико стратегија за то.

Да би се решила већина проблема, сви улазни подаци морају да се прочитају, за шта је потребно време сразмерно величини података. Као резултат, такви проблеми имају најмање линеарну сложеност, или, у великој омега нотацији, сложеност Ω(н).

Неки проблеми, као што су они у компјутерској алгебри и рачунарској алгебарској геометрији, имају веома велика решења. Пошто излаз мора бити написан, сложеност је ограничена максималном величином излаза.

Број поређења потребних за алгоритам сортирања има нелинеарну доњу границу Ω(нлогн). Као резултат тога, најбољи алгоритми за сортирање су најефикаснији јер је њихова сложеност О(нлогн). Чињеница да постоје н! начини организовања н ствари води до ове доње границе. Јер свако поређење дели ову колекцију од н! редоследа на два дела, број Н поређења потребних за разликовање свих редова мора бити 2Н > н!, што имплицира О(нлогн) према Стирлинговој формули.

Свођење проблема на други проблем је уобичајена стратегија за добијање ограничења смањене сложености.

Развој алгоритма

Процена сложености алгоритма је важан елемент процеса пројектовања јер пружа корисне информације о перформансама које се могу очекивати.

Чест је неспоразум да ће, као резултат Муровог закона, који предвиђа експоненцијални раст модерне рачунарске снаге, процена сложености алгоритама постати мање релевантна. Ово је нетачно јер повећана снага омогућава обраду огромних количина података (велики подаци). На пример, било који алгоритам би требало да функционише добро за мање од секунде када сортира по абецедном реду листу од неколико стотина уноса, као што је библиографија књиге. С друге стране, за милион уноса (на пример, телефонски бројеви великог града), основни алгоритми који захтевају О(н2) поређења морали би да изврше трилион поређења, што би трајало три сата при брзини од 10 милион поређења у секунди. Брзо сортирање и сортирање спајањем, с друге стране, захтевају само нлогн поређења (као просечну сложеност случаја за прво, као сложеност најгорег случаја за друго). Ово производи око 30,000,000 поређења за н = 1,000,000, што би трајало само 3 секунде при 10 милиона поређења у секунди.

Као резултат тога, процена сложености може омогућити елиминацију многих неефикасних алгоритама пре имплементације. Ово се такође може користити за фино подешавање сложених алгоритама без потребе за тестирањем свих могућих варијанти. Проучавање сложености омогућава фокусирање напора за повећање ефикасности имплементације одређивањем најскупљих корака сложеног алгоритма.