Complexity - puzzle-uri online

Teoria complexității computaționale - un departament de teorie a calculului al cărui scop principal este de a determina cantitatea de resurse necesare pentru rezolvarea problemelor de calcul. Resursele luate în considerare sunt valori precum timpul, memoria sau numărul procesoarelor.

Juris Hartmanis și Richard Stearns sunt considerați creatorii acestei teorii. Ca exemple de t.z.o. puteți specifica problema de conformitate, cea mai scurtă cale de cale, problema de factorizare și multe altele despre care se știe că sunt computabile. Teoria computabilității, care este a doua ramură importantă a teoriei calculului, tratează problema computabilității.

Rezultatele furnizate de t.z.o. pot fi împărțite în două categorii: pozitive și negative, adică cele care dau ce și cum pot fi calculate și cele în care este dovedit care nu poate fi calculat folosind o anumită cantitate de resurse. Rezultatele pozitive sunt mai ușor de obținut și au de obicei forma unui algoritm care rezolvă o problemă dată împreună cu dovada corectitudinii și o descriere a resurselor necesare.

Complexitatea algoritmilor

Cantitatea de resurse necesare pentru realizarea algoritmului poate fi înțeleasă ca complexitate. În funcție de resursa analizată, vorbim despre complexitatea timpului sau complexitatea memoriei.