Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Polynomial_delay> ?p ?o }
Showing triples 1 to 20 of
20
with 100 triples per page.
- Polynomial_delay abstract "In the analysis of algorithms, an algorithm for listing a large or infinite collection of structures is said to have polynomial delay if the time between the output of any one structure and the next is bounded by a polynomial function of the input size, in the worst case.Polynomial delay implies that the total time used by an algorithm will be polynomial per output item, but is a stronger requirement. This is a desirable property, because it means that any consumer of the stream of outputs will not have to wait idle for a long time from one output to the next. In particular, an algorithm with polynomial delay cannot have a startup phase that takes exponential time before it produces a single output, unlike some algorithms that take polynomial time per output item. Additionally, unlike bounds on the total time, it is a suitable form of analysis even for algorithms that produce an infinite sequence of outputs.The notion of polynomial delay was first introduced by Johnson, Yannakakis & Papadimitriou (1988).".
- Polynomial_delay wikiPageID "47859530".
- Polynomial_delay wikiPageLength "1948".
- Polynomial_delay wikiPageOutDegree "4".
- Polynomial_delay wikiPageRevisionID "681594342".
- Polynomial_delay wikiPageWikiLink Analysis_of_algorithms.
- Polynomial_delay wikiPageWikiLink Best,_worst_and_average_case.
- Polynomial_delay wikiPageWikiLink Category:Analysis_of_algorithms.
- Polynomial_delay wikiPageWikiLink Exponential_time.
- Polynomial_delay wikiPageWikiLink Time_complexity.
- Polynomial_delay wikiPageWikiLink Worst_case.
- Polynomial_delay wikiPageWikiLinkText "polynomial delay".
- Polynomial_delay hasPhotoCollection Polynomial_delay.
- Polynomial_delay wikiPageUsesTemplate Template:Harvtxt.
- Polynomial_delay wikiPageUsesTemplate Template:Reflist.
- Polynomial_delay subject Category:Analysis_of_algorithms.
- Polynomial_delay comment "In the analysis of algorithms, an algorithm for listing a large or infinite collection of structures is said to have polynomial delay if the time between the output of any one structure and the next is bounded by a polynomial function of the input size, in the worst case.Polynomial delay implies that the total time used by an algorithm will be polynomial per output item, but is a stronger requirement.".
- Polynomial_delay label "Polynomial delay".
- Polynomial_delay wasDerivedFrom Polynomial_delay?oldid=681594342.
- Polynomial_delay isPrimaryTopicOf Polynomial_delay.