الأعلى, الأدنى

Question

ماذا يعني أن إثبات الحد الأعلى أو الأدنى إلى خوارزمية ؟

Answer 1

وإثبات الحد الأعلى يعني أنك أثبتت أن الخوارزمية سوف تستخدم لا يزيد بعض الحد على مورد.

وإثبات والأدنى يعني أنك أثبتت أن الخوارزمية سوف تستخدم ما لا يقل عن بعض الحد على مورد.

و"الموارد" في هذا السياق يمكن أن يكون الوقت قد حان، والذاكرة، عرض النطاق الترددي، أو أي شيء آخر.

Answer 2

والعليا والحدود الدنيا لها علاقة مع الحد الأدنى والحد الأقصى "التعقيد" خوارزمية (أنا استخدم تلك الكلمة بروية لأنه له معنى محدد للغاية في تحليل التعقيد).

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

في حالة سيئة بشكل خاص حيث يتم فرز البيانات في مقابل النظام الذي تريد، والوقت الذي يستغرقه يصبح و (ن <سوب> 2 ). وذلك لأن كل تمريرة يتحرك عنصر واحد في المكان المناسب وتحتاج n يمر للقيام بكل العناصر.

في هذه الحالة، الحدود العليا والدنيا مختلفة، على الرغم من أن كبير-O التعقيد لا يزال هو نفسه.

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

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

Answer 3

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

ما أفهمه هو أن مشاكل وقد الأدنى.على سبيل المثال, ونحن نقول أن الدنيا لا بد من المقارنة على أساس الفرز هو \Omega(n log n) ؛ ونحن نبذل أي افتراضات حول ما خاصة المقارنة على أساس الفرز خوارزمية نستخدمها.مهما كانت خوارزمية (دمج النوع نوع سريع, الخ), ونحن لا يمكن أن تفعل أفضل من هذا لا بد من \Omega(n log n).الحدود الدنيا أخبرنا حدسي كم معين المشكلة هو.

عندما نتحدث عن معين خوارزمية, ثم نتحدث عن الحدود العليا.على سبيل المثال, ونحن نقول أن الحد الأعلى من فقاعة نوع O(n^2) العلوي لا بد من دمج النوع O(n log n).الحدود العليا, حدسي, قل لنا كيف جيدة معين خوارزمية هو في حل المشكلة.