Meilleure réponse
Google est votre ami: de Complexité temporelle – Wikipédia
Temps polynomial
Un algorithme est dit de temps polynomial si son temps dexécution est limite supérieure par une expression polynomiale dans la taille de lentrée de lalgorithme, cest-à-dire T ( n ) = {\ displaystyle O (n ^ {k})} pour une constante positive k .
Les problèmes pour lesquels il existe un algorithme de temps polynomial déterministe appartiennent à la classe de complexité P , qui est central dans le domaine de la théorie de la complexité de calcul . La La thèse de Cobham déclare que le temps polynomial est synonyme de « traitable », « faisable », « efficace » ou « rapide ».
Quelques exemples dalgorithmes de temps polynomiaux:
- Lalgorithme de tri de tri de sélection sur n entiers effectue des opérations {\ displaystyle An ^ {2}} pour certaines constantes A . Ainsi, il sexécute dans le temps {\ displaystyle O (n ^ {2})} et est un algorithme de temps polynomial.
- Toutes les opérations arithmétiques de base (addition, soustraction, multiplication, division et comparaison) peuvent être effectuées en temps polynomial.
- Les correspondances maximales dans les graphiques peuvent être trouvées en temps polynomial.
Les
Je pourrais suggérer de suivre quelques cours traditionnels dinformatique tels que les algorithmes utilisant un texte tel que Introduction aux algorithmes ( aka CLRS) même un simple cours sur les structures de données tel que celui décrit dans le article Un cours de CS fondamental qui unit la théorie et la pratique qui utilise le texte classique de Wulf, Shaw, Hilfinger et Flon Structures fondamentales de linformatique .
Réponse
Si nous divisons un polynôme p (x) par un polynôme d (x) alors nous trouvons un quotient q (x) tel que p (x) = d (x) q (x) + r (x) où r (x) est notre reste.
Supposons que r (x) ait un degré ≥︎ n, alors nous aurions pu en modifier davantage étant donné que d (x) est le degré n jusquà ce que notre nouveau r (x) ^ {*} avait un degré strictement inférieur à d (x)
Disons que nous avons p (x) = x ^ 4 + 1 et d (x) = x ^ 2:
x ^ 4 + 1 = x ^ 2q (x) + r (x)
clairement q (x) = x ^ 2
x ^ 4 + 1 = x ^ 2 \ cdot {x ^ 2} + r (x) ⇒︎ r (x) = 1
Maintenant, je pourrais continuer et essayer de dire que q (x) = x et g et:
x ^ 4 + 1 = {x \ cdot {x}} ^ 2+ (x ^ 4-x ^ 3 + 1)
r (x) = x ^ 4-x ^ 3 + 1?
mais ce nest pas du tout ce que nous voulons!
Ceci est analogue à la division / reste en nombres entiers:
p = dq + r
7 = 2 \ cdot {3} +1 est correct
7 = 1 \ cdot {3} +4 nest pas souhaitable car nous navons pas complètement divisé par notre diviseur et laissé un r plus grand que ce que nous devrions avoir.
Le même concept sapplique aux polynômes mais le degré dicte quand vous avez terminé:
\ text {deg} r ( x) text {deg} d (x)
ou vous navez pas entièrement réduit le reste à lélément du degré le plus bas de la classe déquivalence modulo d (x), ou en termes moins mathématiques, vous pouvez trouvez en fait toute une classe de polynômes équivalents lorsque vous modifiez par un polynôme donné, mais vous voulez le plus petit avec un degré pincé entre 0 et n-1 (y compris ces points dextrémité) comme reste.
10 = 7 = 4 = 1 ~ \ text {mod} 3 mais un seul est un cas de reste valide pour une division entière longue!
x ^ 4 + 1 = x ^ 2 + 1 = 1 ~ \ text {mod } x ^ 2 mais un seul est un cas de reste valide pour la division polynomiale longue!
Donc
\ text {deg} r (x) text {deg} d (x)