2个任意算法的时间复杂性分析 - 证明或反驳

Question

我们被给出了2算法A和B，使得对于每个输入大小，算法A执行步骤算法B的数量在相同的输入大小上执行的一半。

我们表示通过 $ g_a（n），g_b（n）$

中每个时间的最严重的时间复杂性

也，我们知道有一个正函数 $ f（n）$ 这样 $ g_a（n）\\ omega（f（n））$

是否可能是 $ g_b（n）\ in \ oomega（f（n））$ ？是必要的吗？

认为这是必要的，但我无法弄清楚与它相矛盾。

Answer 1

是可能的。示例 $ g_a（n）= 1 $ ， $ g_b（n）= 2 $ ，和 $ f（n）= 1 $ 。

也是必要的，因为 $ g_b（n）= 2 g_a（n）\ in \ oomega（f（n））$ 。

要查看 $ 2 g_a（n）\ in \ omega（f（n））$ 您可以使用 $ \ omega（\ cdot）$ 。

从 $ g_a（n）=oomega（f（n））$ 你知道这里是一些 $ n_0 $ 和一些 $ c> 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）\ Omega（f（n））$ 。