الأسوأ هو الأفضل.هل هناك مثال ؟

Question

هل هناك استخداما الخوارزمية التي لديه الوقت تعقيد أسوأ من آخر معروف خوارزمية وإنما هو أفضل اختيار في كل حالات عملية (أسوأ ولكن تعقيد أفضل وإلا)?

إجابة مقبولة قد تكون في شكل:

هناك خوارزميات A و B أن لديك O(N**2) و O(N) الوقت التعقيد في المقابل ، ولكن B وقد الكبير ثابت أنه لا يوجد لديه مزايا أكثر A المدخلات أقل ثم عدد الذرات في الكون.

ومن الأمثلة البارزة عن إجابات:

• البسيط خوارزمية -- أسوأ حالة الأسى الوقت - مقابل المعروف متعدد الحدود-الوقت خوارزميات التحسين محدبة المشاكل.

• ساذجة متوسط المتوسطات خوارزمية -- أسوأ O(N**2) مقابل المعروف O(N) الخوارزمية.

• التراجع regex محركات -- أسوأ الأسي مقابل O(N) طومسون NFA على أساس المحركات.

كل هذه أمثلة استغلال أسوأ مقابلمتوسط السيناريوهات.

هل هناك أمثلة على أن لا تعتمد على الفرق بين أسوأ الأحوال مقابلمتوسط حالة السيناريو ؟

---

ذات صلة:

• صعود `الأسوأ هو الأفضل".(لغرض هذا السؤال "الأسوأ هو الأفضل" عبارة تستخدم في أضيق (وهي -- حسابي الوقت التعقيد) المعنى مما كانت عليه في المادة)

• بايثون فلسفة التصميم:

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

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

• والصفار–فينوغراد الخوارزمية عن مصفوفة مربعة من الضرب هو مثال جيد (وهو أسرع (2008) ولكن هو أدنى إلى أسوأ خوارزميات). أي آخرين ؟ من مقالة ويكيبيديا:"لم يتم استخدامه في الممارسة لأنه يوفر ميزة المصفوفات كبيرة بحيث أنها لا يمكن معالجتها من قبل الأجهزة الحديثة (روبنسون 2005)."

Answer 1

والصفار–فينوغراد الخوارزمية عن مصفوفة مربعة من الضرب.وقتها تعقيد O(n^2.376) مقابل O(n³) من السذاجة خوارزمية الضرب أو مقابل O(n^2.807) بالنسبة شتراسين الخوارزمية.

من مقالة ويكيبيديا:

ومع ذلك, على عكس شتراسين الخوارزمية ، لم يتم استخدامه في الممارسة لأنه يوفر ميزة المصفوفات كبيرة بحيث أنها لا يمكن أن معالجتها بواسطة الأجهزة الحديثة (روبنسون 2005).

Answer 2

سريعة نوعا ما وقد أسوأ الأحوال الوقت تعقيد O(N^2) ولكن عادة ما تعتبر أفضل من غيرها من خوارزميات الفرز التي O(N log n) تعقيد الوقت في أسوأ الأحوال.

Answer 3

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

Answer 4

"الأسوأ هو الأفضل" يمكن أن ينظر إليه في اللغات أيضا ، على سبيل المثال الأفكار وراء Perl, Python, Ruby, Php حتى C# أو جافا أو أيا كانت اللغة التي ليست المجمع أو ج (C++ قد يصلح هنا أو لا).

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Answer 8

هذا المثال سيكون الجواب إذا لم تكن هناك أجهزة الكمبيوتر قادرة على تخزين هذه مجموعات كبيرة.

ويفترض حجم المجموعة 641K.

---

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

العديد من الخوارزميات تم تحسين الأداء على 16bit الحاسوب بدلا من تطويره.هذه أمثلية مناسبة بالكامل 1970s الأجهزة ، ولكن ضعيفا على أكبر مجموعات البيانات على 32 و 64 بت أنظمة محله.إذا كنت اختيار شيء مع أسوأ قابلية الذي يعمل بشكل أفضل على الأجهزة التي تعمل حاليا على أن يكون على علم بأن هذا هو الأمثل ، وأنه قد لا تنطبق في المستقبل.في وقت تلك 1970s إجراءات كتابة البيانات حجم وضعنا لهم في 2000s لم يكن عمليا.للأسف, في محاولة لاستخراج خوارزمية واضحة من تلك الرموز التي ثم يمكن تنفيذها لتناسب الأجهزة الحديثة ليست تافهة.

قصيرة من غليان المحيطات ، ما يعتبر 'جميع الحالات العملية' غالبا ما يعتمد على الزمن المتغير.

Answer 9

ومن الأمثلة على الهندسة الحسابية. المضلع التثليث وقد أسوأ الأحوال O(N) خوارزمية بسبب Chazelle, لكنه تقريبا لم تطبق على أرض الواقع بسبب صلابة من تنفيذ ضخمة ثابتة.

Answer 10

ليس تماما على علامة, ولكن التراجع على أساس التعبيرات العادية بشكل هائل أسوأ الأحوال مقابل O(N) من أجل التنسيق القائم على التعابير العادية ، بعد التراجع القائم على التعبيرات العادية هي دائما تقريبا تستخدم بدلا من وزارة الخارجية-على أساس منها.

تحرير:(JFS)

مطابقة التعبير العادي يمكن أن تكون بسيطة وسريعة (ولكن بطيئة في Java, Perl, PHP, Python, Ruby, ...):

القوة التي backreferences إضافة يأتي بتكلفة كبيرة:في أسوأ القضية المعروفة تطبيقات تتطلب الأسي خوارزميات البحث.

التعبير العادي محركات:

هذا الأسلوب (DFA) هو حقا أكثر كفاءة ، حتى يمكن تكييفها للسماح بالتقاط وعدم الجشع مطابقة, ولكن كما أن لديها أهم السلبيات:

• Lookarounds المستحيل
• مرة أخرى-المراجع أيضا من المستحيل
• Regex قبل تجميع أطول يأخذ المزيد من الذاكرة

على الجانب المشرق ، وكذلك تجنب الأسوأ الأسي تشغيل مرات ، DFA نهج تجنب الأسوأ كومة استخدام الخطية في حجم البيانات المدخلة.

[3]:

Answer 11

يوجد وقت متعدد الحدود خوارزمية لتحديد بريماليتي, ولكن في الواقع, انها دائما أسرع إلى استخدام الأسي الوقت خوارزمية أو لأداء ما يكفي من احتمالي الحسابات لديك ما يكفي من اليقين.

Answer 12

Radix نوع لديه الوقت التعقيد O(ن) على طول ثابت المدخلات ، ولكن فرز سريع في كثير من الأحيان يستخدم ، على الرغم من أسوأ asympotic وقت التشغيل ، لأن لكل عنصر النفقات العامة على الرقم الأساسي النوع هو عادة أعلى من ذلك بكثير.

Answer 13

حسنا, النظر في حل السفر رجل المبيعات المشكلة.على فقط الحل الأمثل هو اختبار جميع المسارات الممكنة.ذلك أن يصبح مستحيلا مع الأجهزة الآجال كما ن الزيادات.لذلك علينا التفكير في العديد من الاستدلال.

وهو ما يقودنا إلى الإجابة على السؤال الخاص بك.الاستدلال (أسوأ) أفضل من القوة الغاشمة عن NP-complete المشاكل.يصف هذا الوضع الذي "الأسوأ هو الأفضل" هو دائما صحيح.

Answer 14

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

يمكنك الحصول على ضمان أسوأ O(n) أداء ثابت من حوالي 40.وهذا ما يسمى متوسط المتوسطات الخوارزمية.في الواقع أنت لن تستخدم هذا.

Answer 15

إذا فهمت السؤال ، تسألون عن الخوارزميات التي هي نظريا ولكن عمليا أسوأ في جميع الحالات.ولذلك لا نتوقع منهم أن يكون في الواقع استخدامها إلا عن طريق الخطأ.

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

ولكن هناك عدة أسباب يمكن أن يخطر لك لا تفعل هذا:

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

2. سيكون من الصعب بناء خوارزمية فعالة للقيام memoiztion من أن الضخمة مشكلة الفضاء.

3. تكلفة التواصل مع المستودع المركزي من المرجح أن تتجاوز تستفيد عدد من العملاء زيادة.

أنا متأكد من أنك يمكن أن نفكر في مشاكل أخرى.

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

---

في استجابة J. F.سيباستيان التعليق:

أعتقد أنه بدلا من عالمي التحفيظ مستودع ، ونحن نعتبر مضروب مستودع.و لن يتحمل نتائج جميع المدخلات الممكنة.بل ستقتصر على النتائج من 1 إلى N! الآن فإنه من السهل أن نرى أن أي جهاز كمبيوتر التي لم factorials أن تستفيد من البحث عن النتيجة بدلا من القيام الحساب.حتى على حساب (N+1)! البحث سيكون مكسبا كبيرا منذ أن حساب من شأنه أن يقلل إلى N!(N+1).

الآن لجعل هذا "أفضل" خوارزمية أسوأ من ذلك ، يمكننا إما زيادة ن أو زيادة عدد أجهزة الكمبيوتر باستخدام المخزون.

ولكن أنا ربما عدم فهم بعض دقة من السؤال.أنها الطريقة أنا أفكر في ذلك انا دائما مع أمثلة هذا مقياس جيد حتى لا.

Answer 16

Mergesort مقابل فرز سريع

نوع سريع متوسط الوقت تعقيد O(n سجل n).يمكن فرز المصفوفات في المكان ، أيمساحة تعقيد O(1).

دمج النوع أيضا متوسط الوقت تعقيد O(n سجل n) ، ومع ذلك الفضاء تعقيد بكثير أسوأ: Θ(n).(هناك حالة خاصة مرتبطة قوائم)

بسبب أسوأ الأحوال تعقيد وقت سريع نوعا هو Θ(n^2) (أيجميع العناصر التي تقع على نفس الجانب من كل محور) ، mergesort هو أسوأ الأحوال O(n سجل n), mergesort هو الخيار الافتراضي على مكتبة والمنفذين.

في هذه الحالة أعتقد أن التنبؤ mergesort أسوأ حالة التعقيد وقت ينسخ quicksorts أقل بكثير من متطلبات الذاكرة.

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

Answer 17

لطالما فهم مصطلح 'أسوأ من الأفضل أن تتصل المشاكل مع الحلول الصحيحة التي هي معقدة جدا حيث تقريبي (أو جيدة بما فيه الكفاية) الحل موجود نسبيا أسهل على الفهم.

وهذا يجعل من الأسهل تصميم وإنتاج وصيانة.

Answer 18

هناك O(n) خوارزمية تحديد ك-ال أكبر عنصر من لم يتم فرزها مجموعة ، ولكن نادرا ما يتم استخدامه بدلا من الفرز, وهو بالطبع O(n logn).

Answer 19

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

Answer 20

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

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

Answer 21

معكرونة النوع هو أفضل من أي خوارزمية الفرز في أنه O(n) إعداد O(1) على تنفيذ O(n) لاستخراج فرز البيانات.فإنه يحقق كل هذا في O(n) مساحة التعقيد.(الأداء الكلي:O(n) في الزمان والمكان على حد سواء.) بعد لأسباب غريبة (واضحة) السبب لا أحد يستخدم أي شيء في كل شيء ، مفضلا أدنى بكثير O(nlogn) خوارزميات وأمثالهم.

Answer 22

التكرارية وتعميق

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

Answer 23

Quick-sort has worst case time complexity of O(N^2)! 
It is considered better than other sorting algorithms 
like mergesort heapsort etc. which have O(N log n) time complexity 
in the worst case.
The reason may be the 
1.in place sorting 
2.stability, 
3.very less amount of code involved.