0

整数O(sqrt(B))であるため、この時間の複雑さを理解するのに苦労しています。B

たとえば、関数がある場合...

int GetResult(int A, int B)
{
}

...そして、この関数の時間計算量はO(sqrt(B))です。時間計算量とは正確には何ですか?

これが少しあいまいな場合は申し訳ありません...他にどのように説明すればよいかわかりません。

4

2 に答える 2

4

時間計算量は、入力データの量に対する関数の実行時間の指標です。

関数の n 個のデータ項目が与えられた場合、

  • O(n) は、関数が各データ項目を「1 回」渡すだけであることを意味します。したがって、入力量を 2 倍にすると、持続時間が 2 倍になります。
  • O(n 2 ) は、たとえば関数がデータに対して 2 つのネストされたループを持っていることを意味するため、入力量を 2 倍にして、4 倍長く待機します。
  • たとえば、O(log n) は対数時間しか必要としません。たとえば、10 倍の入力を与えると、関数は 1 つの「ステップ」だけ長くかかります。
  • したがって、 O(sqrt(n)) は、呼び出しの 4 倍の入力を与えると、関数は 2 倍の時間しかかからないことを意味します。

Big-O-Notation は、関数がどのようにスケーリングするかを示すだけで、実際にかかる時間は示しません。たとえば、Big-O-Notation は定数要素を無視します。たとえば、あるデータを 4 回反復する関数 (順番に 4x ループ) には O(4n) があり、これは O(n) に等しくなります。

この事実は、O(log 10 n) が O(log 2 n ) と等しい理由も示しています: log 10 n = (log 2 n) / (log 2 10)。(log 2 10) は定数であるため、Big-O-Notation では省略できます。したがって、好きなログを選択できますが、Big-O-complexity に関して違いはありません。

リストAとBのように2つの入力がある場合、サイズに2つの変数を使用します.n respとします。メートル。複雑さ O(n^2 * log m) を持つ関数は、次のように動作します。

  • リスト A を 2 倍にすると、実行が大幅に遅くなります (つまり、実行時間が 4 倍になります)。
  • 倍増リスト B は、A の処理時間 O(n 2 )の間、「あと 1 回の繰り返し」だけになります (つまり、n^2 * (任意の未知の定数係数) だけ長くかかります)。
于 2013-10-12T11:54:21.413 に答える
0

あなたの質問に対する答えは B によって異なります。
If B = O(n^4), then O(sqrt(B)) = O(n^2)
If B = O(n^2), then O(sqrt(B) )) = O(n)
B = O(n) の場合、O(sqrt(B)) = O(n^(1/2))

于 2013-10-12T21:25:35.687 に答える