polünoomiliselt

Polünoomiliselt on mõiste, mida kasutatakse matemaatikas ja arvutiteaduses kirjeldamaks suurust, kasvu või ajakulu, mis kasvab või on piiratud polünoomi funktsiooniga sõltuvalt sisendi suurusest n. Üldine tähendus on, et muutujat kirjeldav väärtus areneb mitte kiiremini kui mõni nastmega polünoom.

Formaalne määratlus: kui f(n) kasvab polünoomiliselt, siis leidub konstandid c > 0 ja k ≥ 0 nii, et f(n) ≤ c n^k kõigi piisavalt suurte n jaoks. Arvutusteoorias öeldakse sageli, et algoritmi tööaeg T(n) on polünoomiline, kui T(n) ∈ O(n^k) millelegi konstantile k. See tähendab, et ajakulu kasvab võrdeliselt mõne astmega polünoomiga.

Kasutus ja tähendus: polünoomiline kasv on tavaliselt võrreldud eksponentiaalse ja faktoriaalse kasvuga, mis kasvavad palju kiiremini. Polünoomiline tööaeg on sageli seotud mõistega "köetavaks peetav" või "efektiivne" probleemilahendus, kuigi mõnda probleemi, mis on teoreesis polünoomiline, võib praktikas olla väga suur konstandiga.

Näited: f(n) = 3n^4 + 2n^2 on polünoomiliselt piiratud. Algoritmid, mille tööaeg on O(n^2) või O(n^3), on polünoomilise ajaga, samas kui algoritmid, mille tööaeg on O(2^n) või O(n!), ei ole.

Seosed: polünoomiline kasv on tihedalt seotud mõistega polünoomiline aeg (polünoomne ajastus) ja klassidega nagu P (probleemid lahendatavad polünoomiliselt).