アルゴリズムの解析では、列挙アルゴリズム(つまり、構造体の大規模または無限のコレクションをリストするアルゴリズム) は、任意の 1 つの構造体の出力から次の構造体の出力までの時間が、最悪の場合、入力サイズの多項式関数で制限される場合、多項式遅延があると言われます。[1] 多項式遅延は、アルゴリズムで使用される合計時間が出力項目ごとに多項式になることを意味しますが、より強い要件です。これは、出力ストリームのどのコンシューマーも、1 つの出力から次の出力まで長時間アイドル状態を待つ必要がないことを意味するため、望ましい特性です。特に、多項式遅延のあるアルゴリズムは、出力項目ごとに多項式時間がかかるアルゴリズムとは異なり、単一の出力を生成する前に指数時間を要する起動フェーズを持つことはできません。 [2]さらに、合計時間の制限とは異なり、これは無限の出力シーケンスを生成するアルゴリズムに対しても適切な解析形式です。
多項式遅延の概念は、デイビッド・S・ジョンソン、ミハリス・ヤナカキス、クリストス・パパディミトリウによって初めて導入されました。[2]
参考文献
- ^ Goldberg, Leslie Ann (1991). 組み合わせ構造をリストするための効率的なアルゴリズム. ed.ac.uk (博士論文). エディンバラ大学. hdl :1842/10917. ISBN 9780521117883. OCLC 246835963. EThOS uk.bl.ethos.651566.
- ^ ab Johnson, . S. ; Yannakakis, M. ; Papadimitriou, CH (1988)、「すべての最大独立集合の生成について」、Information Processing Letters、27 (3): 119– 123、doi :10.1016/0020-0190(88)90065-8、MR 0933271。
