Beste antwoord
Google is je vriend: van Tijdscomplexiteit – Wikipedia
Polynoomtijd
Er wordt gezegd dat een algoritme polynoomtijd als de looptijd ervan bovengrens is door een veeltermuitdrukking in de grootte van de invoer voor het algoritme, dwz T ( n ) = {\ displaystyle O (n ^ {k})} voor een positieve constante k .
Problemen waarvoor een deterministisch polynoomtijdalgoritme bestaat, behoren tot de complexiteitsklasse P , die centraal staat op het gebied van computationele complexiteitstheorie . Cobhams proefschrift stelt dat polynoomtijd een synoniem is voor “traceerbaar”, “haalbaar”, “efficiënt” of “snel”.
Enkele voorbeelden van algoritmen voor polynoomtijd:
- Het sorteeralgoritme voor selectie op n gehele getallen voeren {\ displaystyle An ^ {2}} bewerkingen uit voor een constante A . Het loopt dus in de tijd {\ displaystyle O (n ^ {2})} en is een polynoomtijdalgoritme.
- Alle elementaire rekenkundige bewerkingen (optellen, aftrekken, vermenigvuldigen, delen en vergelijken) kunnen worden uitgevoerd in polynoomtijd.
- Maximale overeenkomsten in grafieken kunnen worden gevonden in polynoomtijd.
Ik zou kunnen voorstellen om een paar traditionele cursussen in computerwetenschappen te volgen, zoals algoritmen met een tekst zoals Inleiding tot algoritmen ( ook bekend als CLRS) zelfs een eenvoudige cursus over datastructuren, zoals beschreven in Flons ACM paper Een fundamentele cursus voor informatica die theorie en praktijk verenigt met de klassieke tekst van Wulf, Shaw, Hilfinger en Flon Fundamentele structuren van informatica .
Antwoord
Als we een polynoom p (x) delen door een polynoom d (x), dan vinden we een quotiënt q (x) zodat p (x) = d (x) q (x) + r (x) waar r (x) onze rest is.
Stel dat r (x) graad ≥︎ n had, dan hadden we er meer van kunnen modificeren, gegeven d (x) graad n is totdat onze nieuwe r (x) ^ {*} had een graad die strikt kleiner is dan d (x)
Stel dat we p (x) = x ^ 4 + 1 en d (x) = x ^ 2:
x ^ 4 + 1 = x ^ 2q (x) + r (x)
duidelijk q (x) = x ^ 2
x ^ 4 + 1 = x ^ 2 \ cdot {x ^ 2} + r (x) ⇒︎ r (x) = 1
Nu zou ik kunnen proberen te zeggen dat q (x) = x en g et:
x ^ 4 + 1 = {x \ cdot {x}} ^ 2+ (x ^ 4-x ^ 3 + 1)
r (x) = x ^ 4-x ^ 3 + 1?
maar dit is helemaal niet wat we willen!
Dit is analoog aan deling / rest in gehele getallen:
p = dq + r
7 = 2 \ cdot {3} +1 is correct
7 = 1 \ cdot {3} +4 is niet wenselijk omdat we niet volledig hebben gedeeld door onze deler en liet een grotere r achter dan we zouden moeten hebben.
Hetzelfde concept is van toepassing op polynomen, maar de graad bepaalt wanneer je klaar bent:
\ text {deg} r ( x) text {deg} d (x)
of je hebt de rest niet volledig gereduceerd tot het element van de laagste graad in equivalentieklasse modulo d (x), of in minder wiskundige termen, je kunt vind in feite een hele klasse van polynomen equivalent als je modificeert met een gegeven polynoom, maar je wilt de kleinste met de graad geknepen tussen 0 en n-1 (inclusief die eindpunten) als rest.
10 = 7 = 4 = 1 ~ \ text {mod} 3 maar slechts één is een geldige restletters voor integer staartdeling!
x ^ 4 + 1 = x ^ 2 + 1 = 1 ~ \ text {mod } x ^ 2 maar er is er maar één een geldig restgeval voor de staartdeling van een polynoom!
Dus
\ text {deg} r (x) text {deg} d (x)