Hustá reprezentace

• polynom v jedné proměnné x
  
  $$\sum_{i=0}^n a(i) x^i$$
  
  

• je reprezentován polem všech svých koeficientů a(i), i=0,...,n

• v této reprezentaci potřebujeme pro reprezentování polynomu
  
  2 x¹⁰⁰⁰ - 1
  
  

• uložit 1001 koeficientů čísel a přitom jsou potřeba jen 2 koeficienty; situace pro polynomy ve více proměnných je ještě horší

• složitost algoritmu sčítání dvou polynomů n-tého stupně v této reprezentaci je řádu O(n) , přitom polynomy mohou být vysokého stupně a mohou mít málo členů; většina operací se potom provádí zbytečně (jde o sčítání dvou nul)

• většina polynomů se kterými počítáme je řídká, tj. většina koeficientů je nulových