Polünoomialgoritmid

Polünoomialgoritmid on algoritmid, mille tööaeg on piiratud polünoomilise funktsiooniga sisendi suurusest n. Formaalne defineering: nende aeg on O(n^k) mõne konstantse k jaoks. Sisendi suurus sõltub esitusviisist: näiteks graafi korral on n tavaliselt V+E või V, sõltuvalt sellest, kuidas graaf esitatakse; tekstilise sisendi puhul on n märgistrepli või tähemärkide arv.

Polünoomiline aeg tähendab, et kasv “piiratakse” allpool määratud kiirusega: kui sisendi suurus kasvab, ei kasva aeg kiiremini kui n^k. Tööaeg võib kehtida kõige halvima (worst-case) või mõnel juhul keskmise (average-case) või isegi ootuspärase lahenduse korral.

Näited: sorteerimisalgoritmid nagu mergesort ja heapsort on O(n log n); BFS tööaeg on O(V+E); Dijkstra lühima tee leidmise algoritm graafides on O((V+E) log V). Naive maatriksite korrutamine on O(n^3). Quicksort on keskmiselt O(n log n), kuid halvim juhtum on O(n^2). Kõik need on polünoomsed, kuna neid saab ümbersuunata sobiva k-ga kui vaja.

Teaduslik taust: P on klass, mis sisaldab polünoomiliselt lahendatavaid probleeme. NP on probleemide klass, mida kinnitamine on polünoomne. P ja NP vahelise suhet puudutav küsimus (kas P = NP) on üks keskseid probleeme teoorias, kus vastust ei tea.

Kasutus: polünoomialgoritmid on tavapäraselt eelistatud, kuna neid peetakse tegelikult skaleeritavaks suurte sisendite puhul. Uuringud keskenduvad tihti leidmisele, kas ükskõik millistele probleemidele on olemas polünoomne lahendus või kas efektiivsed heuristikad võivad pakkuda hea lähteväärtuse.