Analyse de la complexité du temps de 2 algorithmes arbitraires - prouver ou réfuter

Question

Nous sommes donnés 2 algorithmes A et B tels que pour chaque taille d'entrée, l'algorithme A effectue la moitié du nombre d'algorithmes d'étapes B effectue une même taille d'entrée.

Nous désignons la complexité patheale de chacun de chacun par $ g_a (n), g_b (n) $

Également, nous savons qu'il y a une fonction positive $ f (n) $ telle que $ g_a (n) \ in\ Oméga (f (n)) $

est-il possible que $ g_b (n) \ in \ oméga (f (n)) $ ?Est-ce nécessaire?

Il semble naïf de penser que c'est nécessaire, mais je ne peux pas comprendre le contredire.

Answer 1

C'est possible. Exemple $ G_A (N)= 1 $ , $ g_b (n)= 2 $ et $ f (n)= 1 $ .

Il est également nécessaire, car $ g_b (n)= 2 g_a (n) \ in \ oméga (f (n) $) $

.

.

pour voir que 2 $ g_a (n) \ in \ omega (f (n)) $ Vous pouvez utiliser la définition de $ \ oméga (\ cdot) $ .

de $ g_a (n)=oméga (f (n)) $ Vous savez que voici quelques $ n_0 $ et certains $ C> 0 $ tel que, $ \ forall n \ ge n_0 $ , $ g_a (n) \ ge cf (n) $ . Cela implique que, pour la même valeur de $ n_0 $ et $ C $ " Conteneur mathématique "> 2 $ G_A (N) \ GE 2 cf (n) \ ge cf (n) $ , c'est-à-dire $ 2 g_a (n) \ in \ Oméga (f (n)) $ .