المحكمة الخاصة بلبنان طلب - الصارم ضعف الطلب

Question

لماذا STL العمل مع المقارنة وظيفة صارمة ضعف الطلب?لماذا لا يمكن أن تكون جزئية الطلب ؟

Answer 1

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

Answer 2

ببساطة، يتم تعريف طلب ضعيف صارم على أنه طلب يحدد العلاقة المعادلة (حسابية). وبعد يتم طلب فصول التكافؤ حسب الطلب ضعيف الصارم: أمر ضعيف صارم هو طلب صارم على فصول التكافؤ.

أمر جزئي (هذا ليس أمرا ضعيفا صارما) لا يحدد علاقة التكافؤ، لذلك أي مواصفات باستخدام مفهوم "العناصر المكافئة" لا معنى لها مع ترتيب جزئي ليس أمرا ضعيفا صارما. تستخدم جميع حاويات STL Associative هذا المفهوم في مرحلة ما، لذلك كل هذه المواصفات لا معنى لها مع أمر جزئي ليس أمرا ضعيفا ضعيفا.

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

منح

• مجموعة رياضية S
• طلب جزئي < على S
• قيمة x في S

يمكنك تحديد قسم S (كل عنصر من عناصر S إما في L(x), I(x) أو G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

يتم فرز التسلسل وفقا < IFF. لكل x في تسلسل، عناصر L(x) تظهر أولا في التسلسل، تليها عناصر I(x), ، تليها عناصر G(x).

تسلسل هو نوع من علمولوجيا IFF. لكل عنصر y التي تظهر بعد عنصر آخر x في التسلسل، y ليس أقل من x. وبعد إنه عائق أضعف من فرزه.

إنه تافهة لإثبات أن كل عنصر L(x) أقل من أي عنصر من عناصر G(x). وبعد لا توجد علاقة عامة بين عناصر L(x) وعناصر I(x), ، أو بين عناصر I(x) وعناصر G(x). وبعد ومع ذلك، إذا < هو طلب ضعيف ضعيف، من كل عنصر L(x) أقل من أي عنصر من عناصر I(x), ، وعن أي عنصر من عناصر I(x) أقل من أي عنصر من عناصر G(x).

إذا < هو أمر ضعيف ضعيف، و x<y ثم أي عنصر من عناصر L(x) U I(x) أقل ثم أي عنصر I(y) U G(y): أي عنصر غير أكبر من x أقل من أي عنصر لا تقل عن ذلك y. هذا لا يمسك بالضرورة أمر جزئي.

Answer 3

نقلا عن جواب هنا:

لأن داخليا ، هذه الخوارزميات تنفيذ "يساوي" كما !(a < b) && !(b < a).

إذا كنت تستخدم <= لتنفيذ أقل من المشغل ، ثم فوق أن return false عندما a == b.كسر المساواة تحقق سوف المسمار أي ما يقرب من الخوارزمية.

كما أنها تنفذ "لا يساوي" كما (a < b) || (b < a) و مرة أخرى, إذا كنت تنفذ < المشغل باستخدام <=, ، ثم العودة الحقيقية عندما قدم المساواة مع بعضها البعض, في حين أنها ليست متساوية.وبالتالي فإن المساواة تحقق هو كسر في كلا الاتجاهين.

كل نقطة من الحد من المكتبة إلى أقل من المشغل أن جميع المعاملات المنطقية يمكن تنفيذها من حيث أنها:

• <(a, b): (a < b)
• <=(a, b): !(b < a)
• ==(a, b): !(a < b) && !(b < a)
• !=(a, b): (a < b) || (b < a)
• >(a, b): (b < a)
• >=(a, b): !(a < b)

يعمل هذا طالما قدمت المشغل يلبي شروط صارمة ضعف الطلب.القياسية <= و >= المشغلين لا.

Answer 4

لا يمكنك إجراء بحث ثنائي مع الطلب الجزئي. لا يمكنك إنشاء شجرة بحث ثنائية مع طلب جزئي. ما وظائف / أنواع البيانات من خوارزمية بحاجة إلى طلب ويمكن أن تعمل مع الطلب الجزئي؟