كيف f (n)

Question

لقد كنت أقرأ هذا البرنامج التعليمي في التعقيد الزمني ، وأنا في حيرة بعض الشيء على شرحه $ O $ التدوين. يكتب:

$ O (g (n))= $ { $ f (n) $ : هناك توجد ثوابت إيجابية $ C $ و $ n_0 $ مثل $ 0 \ leq f (n) \ leq c * g (n) $ لجميع $ n> n_0 $ .

الطريقة التي أفهمها، $ c * g (n) $ الدلائل $ c $ مضروبة بواسطة $ g (n) $ . إذا كان هذا هو الحال، فماذا تحدد التعبير أعلاه الوقت، وليس فقط أن $ c * g (n) $ أكبر من $ f (n) $ ؟ أو أنا غير صحيح، وهذا هو بعض التدوين لا أفهم؟ فهمي للوقت التعقيد هو بدائي للغاية، لذا اغفر لي إذا كان هذا خطأ غبي في قلبي.

Answer 1

كيف f (n)

لا. Bachmann-Landau Netation هو ببساطة طريقة مفيدة لمقارنة معدل نمو الوظائف. لا يقول أي شيء عن ما تعني هذه المهام ، ويمكننا أن نكون متأكدين من أن باخمان لم يفكر في أجهزة الكمبيوتر عندما توصل إلى ذلك في عام 1894.

ما معنى قمت بتعيينها لتلك الوظائف متروك لك. على سبيل المثال، عند تحليل خوارزميات الفرز القائمة على المقارنة، نأخذ عادة $ n $ ليكون عدد العناصر في المجموعة و $ f (n) $ ليكون عدد المقارنات، أو عدد المقايضات، أو عدد المقارنات والقائمة.

لاحظ أيضا أن كل هذا هو دائما بالنسبة لطراز الجهاز أو نموذج التكلفة.

كمثال بسيط للغاية، إذا كنت سأطلب منك ما هي تعقيد الخطوة الأسوأ للقضارات لنسخ قائمة، فستقول $ O (n) $ . ولكن في الواقع، سيكون الإجابة الصحيحة "لا يمكنني إخبارك بذلك لأنك لم تحدد طراز الجهاز". لأنه، على سبيل المثال، في آلة تورينج، نسخ قائمة $ O (n ^ 2) $ ، لأنه لكل عنصر يتم نسخه، رأس TM لديه للقيادة أكثر وأكثر وأكثر للوصول إلى نهاية القائمة لكتابة العنصر التالي.

Answer 2

تقول أن وقت التشغيل في الخوارزمية في $ O (g (n)) $ يعطي، كما لاحظت، فقط ملزمة أعلى. علاوة على ذلك، يتم منح الحد العلوي مع الثوابت $ C $ و $ n_0 $ غير معروف. لذلك نعم، إنها معلومات ضعيفة إلى حد ما عن وقت التشغيل.

ثابت $ C $ يمكن أن يحتوي على معلومات حول التكلفة الحقيقية للعمليات الأساسية للخوارزمية، والتي يمكن أن تكون غير معروفة و / أو متغير بين المدى، ولكن لا يزال معروفا بتكلفة مقدار الوقت المحدد. ينعكس الحاوية غير المحددة $ n_0 $ أن المرتبط المعطى يشير إلى أحجام كبيرة من المدخلات (أو أي المعلمة $ n $ < / span> يمثل).

href="https://en.wikipedia.org/wiki/big_o_notation#family_of_bachmann٪e2٪80٪93landau_Notations" rel="nofollow noreferrer"> يتم استخدام الرموز الأخرى لإعطاء أنواع أخرى أو معلومات أكثر دقة حول وقت التشغيل.