لماذا دراسة نظرية التعقيد؟

Question

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

على سبيل المثال، من المعروف أنه يمكن تطوير خوارزمية لتحديد لعبة شطرنج مثالية $O(1)$, حيث أن عدد مباريات الشطرنج القانونية على شبكة 8×8 محدد من الأعلى.ومع ذلك، فقد سمعت أن هذه الخوارزمية ستستغرق وقتًا أطول من عمر الكون حتى تنتهي.وهذا يطرح السؤال، لماذا نظرية التعقيد؟يبدو لي أن هذا المجال معيب بشكل أساسي، ويجب على علماء الكمبيوتر استخدام نهج أفضل لدراسة الخوارزميات.

(ملحوظة:خالص اعتذاري للباحثين في هذا المجال.☻)

Answer 1

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

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

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

يمكننا بالمثل مناقشة كل موضوع من المواضيع الأخرى - على سبيل المثال، لماذا أو لماذا لا ندرس نظرية التعقيد - وستجد أن لديهم أيضًا فروق دقيقة.

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

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

أنصحك بشدة بقراءة المصادر التالية، لأنها وثيقة الصلة بسؤالك: لماذا يسمى الوقت متعدد الحدود "فعال"؟, شرح أهمية التعقيد المقارب للخوارزميات لممارسة تصميم الخوارزميات, مبرر إهمال العوامل الثابتة في Big O.