2

したがって、プログラミングコンテスト（ACM ICPCなど）からいくつかの練習問題を経験していたとき、人々はしばしばO（N ^ 2）ソリューション、またはさらに悪いことに、ヒープ（C ++のpriority_queue）またはdequeを使用することができます複雑さを軽減します。（ある種の最適化として、パターンの「何か」に気付いた後）

たとえば、「スライディングウィンドウの最大値」の問題では、次のようになります。

For each window of size K in an array of size N, compute the maximum.

些細なO（NK）アルゴリズム、かなり簡単なO（nlogn）ソリューション（ヒープを使用してそれを見ることができます）、および両端キューを使用するO（N）ソリューションがあります。

これらのプリンシパルは、役に立たない値を「捨てる」、またはプロパティ（最大、累積合計、最小など）を見つけるために領域を照会するというプリンシパルにあるようです。

たとえば、一部のO（N ^ 2）アルゴリズムをO（NlogN）に変換する場合、前のN個の要素すべてをループして最大値を見つける代わりに、priority_queueを使用して、特定のウィンドウ内で値が取得されるまで値をポップアウトし続けることができます。 。

誰か良いヒントがありますか？（もっと問題を起こす以外に...私はそれをやろうとしています）

4

1 に答える 1

0

DPアルゴリズムの基本は分割問題です。

時間計算量を減らすために、別の方法で問題を分割しましょう。

DPアルゴリズムを具体化するために、ソート、ツリー（アルゴリズムではない場合でも）などの多くの簡単なサブアルゴリズムを使用します...

時間の複雑さを軽減したい場合は、このアルゴリズムをより高速に具体化します。

ソートを使用している場合は、選択/バブルソートの代わりにクイックソートまたはヒープソートを使用してください。

最小/最大値を取得する場合は、ヒープまたは優先キューを使用します。

より高速な漸化式を作成できない場合は、より高速なサブアルゴリズムを使用して時間を短縮します。

于 2012-10-18T09:00:02.057 に答える