6

ここには SO に関する多くの関連する質問がありますが、それらはすべて、任意のアルゴリズムの複雑さを計算するプログラムを作成することについて質問しています (これは明らかに判断できません)。入力に対して次の制限を設けます。

  1. アルゴリズムは終了します
  2. アルゴリズムは純粋に機能的です

問題は、静的解析を通じてそのようなアルゴリズムの時間計算量を計算するプログラムを作成できるかということです。入力アルゴリズムが終了しない場合、プログラムの動作は未定義です (クラッシュするか、嘘を返すか、終了に失敗する可能性があります)。

4

3 に答える 3

1

実際の実行時間に基づいて複雑さを推定する手法から正しい答えを得ていると 100% 確信することはできません。これは、正確な実行時間には非常に複雑な関数が含まれる可能性があるためです。つまり、入力サイズが非常に大きな数値を下回っている間、実行時間は理論的には他の関数に従うことができます。入力サイズが無限大に向かう傾向があるため、実行時間は複雑度関数 (の倍数) に向かう傾向があるだけです。これは、上限または下限だけでなく、タイトな境界(すべてではありませんが、多くのアルゴリズムに存在します)を見つけたいと想定しています。

しかし、一般的に非常に正確な複雑さの合理的な見積もりを思い付くことができます。

また、多くのアルゴリズムでは、同じサイズの異なる入力に対して実行時間が異なることに注意してください。同じサイズのいくつかの異なる入力に対して以下を実行し、結果を平均してこれを軽減することができます。これは、実行時間に影響を与える可能性のあるシステム条件を軽減するのにも役立ちます. ただし、それらに使用する特定の入力がわからない場合は、最悪のケースと最良のケースの複雑さを見積もることができない場合があります (ランダム データを渡すときにそれらを取得するには稀すぎる可能性があるため)。

これを行う方法：

十分に大きく、十分に異なるサイズの入力の時間を記録します (たとえば、100、1000、10000 など、10 の異なるべき乗に等しいサイズの入力に対して実行できます。これらは、少なくとも 1 回実行するのに十分な大きさである必要があります)。データのノイズを少なくするには数秒かかります)。3 つの入力サイズを使用してみましょう。厳密に言えば、必要な入力サイズは 2 つだけですが、追加の検証として 3 つ以上を使用できます。

これで、取得したこれら 3 つの結果を、 、 、 、 、 、 などの複雑さのセットの 1 つにO(1)マッピングO(log(n))するO(sqrt(n))ことO(n)がO(n log n)できます。O(n2)O(n3)

手動で一致させようとしている場合は、取得した実行時間を上記の各関数のグラフ (適切にスケーリングされたもの) と一緒にグラフに表示し、どれが最も一致するかを確認できます。

自動化しようとしている場合は、各関数を入力サイズにマップして、どれだけ一致するかを確認できます。

これを行うにはもっと良い方法がありますが、非常に簡単な方法の 1 つは次のようになります。

これらの実行時間があるとします。

input size   running time
100          21 seconds
1000         29 seconds
10000        40 seconds

これで、それらの 1 つ (最も正確である可能性が高い最大のもの) を上記の関数の 1 つの倍数に一致させることができます。

O(n):     k x n     = k x 10000     = 40,    k = 40 / 10000     = 0.004
O(log n): k x log n = k x log 10000 = 40,    k = 40 / log 10000 = 10
O(n²):    k x n²    = k x 10000²    = 40,    k = 40 / 10000²    = 0.0000004

次に、式から得られるものと、他の入力サイズの実際の実行時間とを比較します。

For n = 1000, actual running time = 29 seconds
O(n):     0.004 x 1000      = 4 seconds
O(log n): 10 x log 1000     = 30 seconds
O(n²):    0.0000004 x 1000² = 0.4 seconds

For n = 100, actual running time = 21 seconds
O(n):     0.004 x 100      = 0.4 seconds
O(log n): 10 x log 100     = 20 seconds
O(n²):    0.0000004 x 100² = 0.004 seconds

これを見るO(log n)と、実際の実行時間と予測された実行時間の差がどちらの場合もわずか 1 秒で、これが最も近いことがはっきりとわかります。したがって、それが複雑さの推測になります。

于 2013-01-04T19:39:20.087 に答える
1

私は最終的に適切な場所で質問し、答えを得ました。いいえ。

https://cstheory.stackexchange.com/questions/14969/algorithmically-compute-a-reasonable-bound-on-the-runtime-of-an-algorithm#comment40524_14969

于 2013-01-04T22:17:56.597 に答える
0

アルゴリズムが停止するという制限を考えると、それは可能です。可能な入力ごとにアルゴリズムを実行し、実行時間を測定します。次に、可能な上限として関数を選択し、結果ごとにテストします。十分でない場合は、境界を増やして再テストします。境界が十分になるまで繰り返します。

編集：このソリューションは、実際のコンピュータープログラムの境界を想定しています。つまり、さまざまな入力の量は無限ではありません。そうでなければ、一般的なアルゴリズムの複雑さを計算することはできません。複雑さが であるアルゴリズムを考えてみましょうO(n) = nO(n-1)。f入力が無限であるため、複雑さを制限できる関数を見つけることができません。

于 2012-11-14T05:49:06.257 に答える