0

アルゴリズムが提示されたときにアルゴリズムの時間計算量を見つける方法は理解していますが、アルゴリズムが与えられた回数を与えられたときにそれを解決する方法について頭を悩ませているようには見えません実行され、かかった時間。

O（n）、O（n）、O（n ^ 2）のような明らかなものである場合、私は時々それを得ることができますが、この質問を例に取ってください：

アルゴリズムは、サイズnの特定の入力を実行します。nが4096の場合、実行時間は512ミリ秒です。nが16384の場合、実行時間は1024ミリ秒です。nが36864の場合、実行時間は1536ミリ秒です。

時間計算量とは何ですか？

私はそれをn*2、t * 1.5と見ていますが、それをどのように解決するかはよくわかりません。

ご協力ありがとうございました ：）

4

3 に答える 3

2

アルゴリズムだけでなくシステムが複雑なため、この種の質問には3つ以上のデータポイントが必要だと思います。

私が行うことは、反復と経過時間を比較し、標準時間計算量の1つに一致するパターンを見つけることができるかどうかを確認することです。

  • 定数：O（c）ここで、cは定数です。
  • 線形：O（n）
  • 多項式：O（n ^ c）ここで、cは定数（またはO（n ^ 2 + n ^ 6）のような複雑なもの）です。
  • 指数関数：O（c ^ n）ここで、cは定数です。
  • 対数：O（log | n |）
  • これが何と呼ばれるか：O（n log | n |）

あなたの問題を調べてみましょう：

n     | time
4096  | 512 ms
16384 | 1024 ms
36864 | 1536 ms

nが4倍（4096から16384）上がると、時間は2倍（512から1024ミリ秒）上がります。

nが9倍（4096から36864）上がると、時間は3倍（512から1536ミリ秒）上がります。

これに一致する関数はf（n）= n ^（1/2）です。nが4倍になると、f（n）はsqrt（4）の倍になります。

したがって、これは次数O（n ^ .5）であり、多項式です。

TLDR：グラフ化して、時間計算量の一般的な関数と一致させます。現実の世界では、おそらく3つ以上のデータポイントが必要になります。

編集：これは本当にもっと複雑なはずだということを付け加えたいと思います。あらゆる種類の時間計算量には定数項が存在する可能性があります。つまり、O（n ^ c）はO（n ^ c + K）である可能性が高くなります。ここで、Kは定数です。これを書き出すときは、簡単にするために定数を無視しますが、グラフに表示されます。

于 2012-10-13T22:54:29.947 に答える
0

実際のアルゴリズムがわからない場合は、折れ線グラフを作成し、nグラフの下部に表示し、yその数値の実行にかかった時間になります。

線の傾きが0の場合はO（1）、線形の場合はO（n）、曲線の場合はO（n ^ 2）、O（log n）、またはその他のいずれかです。非線形の時間計算量。

于 2012-10-13T22:46:27.840 に答える
0

アルゴリズムの時間計算量がである場合、入力の時間のn^x商はt_2 / t_1n_1n_2

(t_2 / t_1) = (n_2 / n_1)^x

対数を取ると、

log (t_2 / t_1) = x * log (n_2 / n_1)

そして解決することができますx：

x = log (t_2 / t_1) / log (n_2 / n_1)

あなたの例では、n_1 = 4096とt_1 = 512msで、商を取得します

16384 / 4096 = 4        36864 / 4096 = 9
 1024 / 512  = 2         1536 / 512  = 3

そうx = 1/2。

複雑さが純粋なべき乗則に従わない場合は、十分な数のそのような商を評価することでべき乗則を推定できます。複雑さが実際に指数関数的（または超指数関数的）である場合、商は線形または超線形に成長します。次に、成長率を使用して、指数の場合の指数のベースを見つけることができます。

于 2012-10-13T22:49:26.620 に答える