2つの任意のアルゴリズムの時間の複雑さ解析 - 証明または不審

Question

2つのアルゴリズムAとBが与えられて、入力サイズごとに、アルゴリズムAは同じ入力サイズで実行されるステップアルゴリズムBの数を半分に実行するように与えられます。

$ g_a（n）、g_b（n）$

の最悪の時間の複雑さを表します。

また、 $ g_a（n）\ inなど、正の関数 $ f（n）$ があります。\ OMEGA（f（n））$

$ g_b（n）\ inmega（f（n））$ の

必要ですか？

それが必要だと考えるのは素朴そうですが、それに矛盾するために理解することはできません。

Answer 1

可能です。例 $ g_a（n）= 1 $ 、 $ g_b（n）= 2 $ 、およびspan class="math-container"> $ f（n）= 1 $ 。

$ g_b（n）= 2 g_a（n）\ inmega（f（n））$ 。

その $ 2 g_a（n）\ inmega（f（n））$ の定義を使用することができます。 $ \ omega（\ cdot）$ 。

$ g_a（n）=omega（f（n））$ は、ここにある $です。 N_0 $ といくつかの 0 $ 、 $ \ forall n \ ge n_0 $ 、 $ g_a（n）\ \ ge cf（n）$ 。 これは、同じ値の $ n_0 $ 、 $ c $ 、 $ 2 g_a（n）\ ge 2 cf（n）\ ge cf（n）$ 、つまり $ 2 g_a（n）\ in \ OMEGA（F（n））$ 。