تحليل تعقيد الوقت ل 2 خوارزميات تعسفية - إثبات أو دحض

Question

نحن نحصل على خوارزميات 2 A و B بحيث تكون في كل حجم الإدخال، تقوم خوارزمية بإجراء نصف عدد خوارزمية الخطوات التي تعمل على نفس حجم الإدخال نفسه.

نشير إلى أسوأ تعقيد وقت لكل واحد بواسطة $ g_a (n)، g_b (n) $

أيضا، نحن نعلم أن هناك وظيفة إيجابية $ f (n) $ مثل $ g_a (n) \ in\ أوميغا (F (n)) $

هل من الممكن أن $ g_b (n) \ in \ omega (f (n)) $ ؟هل هو ضروري؟

يبدو ساذجا أن تعتقد أنه من الضروري، لكنني لا أستطيع معرفة ذلك لتناقضه.

Answer 1

ممكن. مثال $ g_a (n)= 1 دولار ، $ g_b (n)= 2 دولار ، و $ f (n)= 1 $ .

هو أيضا ضروري أيضا، لأن $ g_b (n)= 2 g_a (n) \ in \ omega (f (n)) $ .

.

لمعرفة ذلك $ 2 g_a (n) \ in \ omega (f (n)) $ يمكنك استخدام تعريف $ \ أوميغا (\ cdot) $ .

from $ g_a (n)=omega (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) \ in \ أوميغا (F (n)) $ .