Next: Rekursivní reprezentace
Up: Reprezentace polynomů
Previous: Hustá reprezentace
Řídká reprezentace
- polynom v jedné proměnné
x
- je reprezentován dvojicemi exponentů a koeficientů
(i a(i))
pro každý člen vyskytující se v polynomu, tj. všechny
koeficienty
a(i) v této reprezentaci jsou nenulové
- dvojice jsou uspořádány podle exponentu
- v této reprezentaci bude polynom
2 x1000 - 1
- reprezentován seznamem
( (1000 2) (0 -1) )
- složitost algoritmu sčítání dvou polynomů s n členy je
O(n)
- pro efektivnost algoritmů je v řídké reprezentaci většinou zvoleno
pravidlo určující, že v seznamu jsou dvojice uspořádány podle
exponentu, např. od největšího exponentu k nejmenšímu jako v příkladu
výše
Richard Liska