2

N の関数としてプログラムの時間を計測し、次の表を作成するとします。

        N   seconds
-------------------
    19683      0.00
    59049      0.00
   177147      0.01
   531441      0.08
  1594323      0.44
  4782969      2.46
 14348907     13.58
 43046721     74.99
129140163    414.20
387420489   2287.85

実行時間の増加の順序を N の関数として推定します。実行時間はべき法則 T(N) ~ a N^b に従うと仮定します。答えとして、定数 b を入力します。あなたの答えが目標の答えの 1% 以内であれば、正解としてマークされます - 小数点の後に 2 桁の数字を使用することをお勧めします (例: 2.34)。

誰かがこれを計算する方法を説明できますか?

4

2 に答える 2

3

1.ある行から次の行への成長の変化の比率を計算する必要があります

N          seconds  
--------------------
14348907    13.58   
43046721    74.99   
129140163   414.2   
387420489   2287.85

2.Nの変化率を計算する

43046721 / 14348907 = 3
129140163 / 43046721 = 3

したがって、N の変化率は 3 です。

3.秒単位の変化率を計算する

74.99 / 13.58 = 5.52

ここで、行のもう 1 つのペア間の比率を確認してみましょう。

414.2 / 74.99 = 5.52

したがって、秒の変化率は 5.52 です。

4.次の等式を作成します

 3^b = 5.52
 b = 1.55

最後に、実行時間の増加の順序は 1.55 であることがわかります。

于 2015-02-06T01:16:27.313 に答える