Polynomiální zpoždění - Polynomial delay - Wikipedia

V analýza algoritmů, an enumerační algoritmus (tj. algoritmus pro výpis velké nebo nekonečné kolekce struktur) se říká, že má polynomiální zpoždění je-li čas mezi výstupem kterékoli struktury a další omezen polynomiální funkcí velikosti vstupu, v nejhorší případ.[1]Polynomiální zpoždění znamená, že celková doba použitá algoritmem bude polynomická na výstupní položku, ale je silnějším požadavkem. Toto je žádoucí vlastnost, protože to znamená, že žádný spotřebitel proudu výstupů nebude muset dlouho čekat nečinný z jednoho výstupu na druhý. Zejména algoritmus s polynomickým zpožděním nemůže mít spouštěcí fázi, která trvá exponenciální čas před tím, než vytvoří jeden výstup, na rozdíl od některých algoritmů, které vyžadují polynomiální čas na výstupní položku.[2] Navíc, na rozdíl od hranic celkového času, je to vhodná forma analýzy i pro algoritmy, které vytvářejí nekonečnou sekvenci výstupů.

Pojem polynomiální zpoždění poprvé představil David S. Johnson, Mihalis Yannakakis a Christos Papadimitriou.[2]

Reference

  1. ^ Goldberg, Leslie Ann (1991). Efektivní algoritmy pro výpis kombinačních struktur. vyd. ac.uk (Disertační práce). University of Edinburgh. hdl:1842/10917. ISBN  9780521117883. OCLC  246835963. EThOS  uk.bl.ethos.651566.
  2. ^ A b Johnson,. S.; Yannakakis, M.; Papadimitriou, C. H. (1988), „O generování všech maximálních nezávislých množin“, Dopisy o zpracování informací, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8, PAN  0933271.