c# - Big-O 表記を使用した時間計算量

Question

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

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

int GetResult(int A, int B)
{
}

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

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

Answer 1

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

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

• O(n) は、関数が各データ項目を「1 回」渡すだけであることを意味します。したがって、入力量を 2 倍にすると、持続時間が 2 倍になります。
• O(n ² ) は、たとえば関数がデータに対して 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 ₁₀ n = (log ₂ n) / (log ₂ 10)。(log ₂ 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 * (任意の未知の定数係数) だけ長くかかります)。

Answer 2

あなたの質問に対する答えは 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))