algorithm - 多項式時間アルゴリズム

Question

私は一度次の引用を聞いたが、それが誰に起因するのかを忘れた：

（多項式時間）アルゴリズムが停止するのを待っている間、あなたの寿命も多項式によって制限されることを忘れないでください。

誰かが参照を提供できますか？

私が持っている別の質問は次のとおりです。多項式時間アルゴリズムは素晴らしいですが、実際に使用されるアルゴリズムの例は何O(n^101)ですか？つまり、高度な多項式に制限されていますか？

Answer 1

さて、私はO（n ^ 101）を見たことがありませんが、他のわずかに低次のアルゴリズムを組み合わせて、不注意に高次のアルゴリズムを作成するのが一般的です。私の経験では、複雑さが1つの変数に限定されることはめったになく、複数の変数で表現されることがよくあります。たとえば、O（A * log（B）log（C）（D ^ 2）*（EF））

例として、私は最近、（N）3d座標で構成される（X）x（Y）メートルの面積を持つ特定の地形モデルの揚水発電所のすべての潜在的なサイトを見つけるアルゴリズムを開発するように任命されました。要件は、指定された最大水平距離（H）内の指定された最小面積（A）のフラット領域を見つけることであり、別のフラットの最小高さ差（Z）は指定された最小サイズです。このコンテキストでの平坦度は、垂直間隔（V）で検索された、領域を任意の高さ（E）に水平にするために移動する必要があるマテリアルのボリュームとして定義されます。エリアは直径（D）の（S）辺のポリゴンとして定義され、検索解像度はメートル（M）で指定されました。強引な複雑さは、非常に大まかに次のようになります。

1）初期平坦領域= O（（X / M）*（Y / M））を線形スキャンします。この領域の高さ範囲はZ1からZ2になります。2）現在の位置で平坦度を計算し、単一ボリュームO（S）を計算します。 、最小体積で高さを検索O（（（Z2-Z1）/ V）* S）3）現在の平坦領域O（D / M）に近い別の平坦領域を放射状にスキャンし、新しい平坦領域を計算しますエリアO（（Z3-Z4）/ V）* S）

これを組み合わせると、O（（X / M）（Y / M）（（Z2-Z1）/ V）S（D / M）（H / M）（（Z3-Z4）/ V）* S）とより良いアプローチの明らかな必要性;）

この場合、検索内で検索する必要があるため、複雑さが生じます。たとえば、地形内のフラットスポットの検索では、フラットスポットの定義自体に重要な検索が必要であり、その結果、検索が増える可能性があります。これは避けられない場合があり、望ましくないレベルの複雑さにつながります。

ここでは、抽象化が敵になることがよくあります。この場合、1つの反復ライブラリルーチンが別の反復ライブラリルーチンを繰り返し使用し、それが独自のコードで繰り返し使用されます。コンテナクラスの不適切な選択は、特に他のコンテナを含むコンテナにぶつかった場合に、ここでよくある落とし穴です。

Answer 2

ほとんどの場合、複雑さO（n ¹⁰⁰）のアルゴリズムはまったく実用的ではありません。これは、そのようなアルゴリズムが実際に使用されない理由を説明しています。

高多項式アルゴリズム問題の繰り返し発生するファミリの1つは、オブジェクトの大規模なコレクション（N個のオブジェクト）があり、特定の任意のメトリックに従ってコレクションからk個の要素の「最適な」サブセットを見つける必要がある場合、または特定のプロパティを持つk個の要素のサブセット。常に適用できる唯一の解決策は、考えられるすべてのサブセットを列挙することです。これにより、すぐにO（N ^k）の複雑さが生じます（kは固定されています）。ただし、k = 100の場合は想像が難しく、Nのほとんどの値について実際に解決することはできませんでした。