complexity-theory - 2n^2 + n の複雑さ

Question

複雑な問題が の2n^2 + n24 単位時間で解決できる場合、n = 2はどのくらいの時間がかかりn = 4ますか?

答えは 48 だと言われましたが、アルゴリズムの複雑さから 24^2 であるべきだと思いますO(n^2)。

誰かが私を啓発できるかどうかに感謝します。

Answer 1

ビッグオー記法は漸近記法です。厳密に言えば、f(n)=O(n^2) は、n >= n0 に対して、An^2 <= f(n) <= Bn^2 となる A,B の実数と n0 個の整数が存在することを意味します。

したがって、最初に n < n0 の場合、トレンドは n^2 に従う必要さえありません。次に、n >= n0 の場合、f(n) が制限されていることのみが保証されます (上記のとおり)。近似したい場合、O(n^2) は、n が大きい場合は低次の項を削除できることを意味します (f(n) --> 2n^2)。ただし、n が小さい場合、これは重大なエラーを引き起こします。

あなたの場合、パフォーマンスの正確な関数形式 f(n) = 2n^2+2 があるので、それを使用する必要があります!

各ステップに T0 の時間がかかり、一定時間 C の場合、T(n) = T0*(2n^2+n) + C であると仮定します。C = 0の場合、次のようになります。

1. T0 を求める: T(2) = 24 = T0*(2(2)^2+2) => T0 = 2.4 時間
2. n=4 の場合は T0 を使用、T(4) = (2.4 時間)*(2(4)^2+4) = 86.4 時間

Answer 2

複雑さ O(f(n)) は、c*f(n)+d 時間かかるすべての計算で構成されます。ここで、c と d は定数です。d=0 の場合:

n=2 で複雑度 O(2n^2+2) が 24 の場合:

24 = (2*2^2 + 2)*c なので、c = 24/10 = 2.4

ここで、n=4 について計算します。

(2*4^2+4)*2.4= 36*2.4 = 86.4 単位の時間

d が 0 でない場合、c = (24-d)/10 となり、n=4 の場合は次のようになります。

36*(24-d)/10 +d = 86.4 +0.9d

したがって、答えが 48 になることはあり得ません。これは、さらに線形アルゴリズムを意味します。

Answer 3

Ruby を数学言語として使用すると、OP の式は次のようになります。

f = -> x { 2 * x ** 2 + x }

(1) アルゴリズムの 1 ステップに 1 単位の時間がかかると仮定すると50、定数項cが

c = 24 - f.( 2 ) #=> 10
# and
c + f.( 4 ) #=> 50

この仮定の下では、答えは 50 です。

(2) ただし、アルゴリズムの 1 つのステップにe1 時間単位ではなく時間単位を使用できるようにすると、定数cは次のようになります。

24 - e * 10

の実行時間n == 4は

24 + e * 26        # gives 50 for e == 1

(3) 定数時間が 0 である (つまり、与えられた式は正確なである) という追加の仮定により、次のようになります。

24 - e * 10 == 0

Candide、bcorso、およびMilky Dinescuによる回答が適用されます。

OPの質問は文字通り1ステップ== 1時間単位とは述べていませんが、典型的で確認しやすい教科書の結果に基づいて、これは著者の意図であると感じてい50ます。