أساسيات نظرية التعقيد الحسابي EITC/IS/CCTF

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

الوقت هو المورد الأكثر اعتبارًا عادةً. عندما يُستخدم مصطلح "التعقيد" بدون محدد ، فإنه يشير عادةً إلى تعقيد الوقت.

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

مورد مهم آخر هو مقدار ذاكرة الكمبيوتر المطلوبة لتنفيذ الخوارزميات.

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

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

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

المورد الذي غالبًا ما يتم اعتباره في الفرز والبحث هو مقدار مقارنات الإدخالات. إذا كانت البيانات مرتبة جيدًا ، فهذا مؤشر جيد على تعقيد الوقت.

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

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

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

لهذه الأسباب ، يتم إيلاء معظم الاهتمام لسلوك التعقيد لـ n عالية ، أي سلوكها المقارب حيث تقترب n من اللانهاية. نتيجة لذلك ، يتم استخدام تدوين O الكبير بشكل شائع للإشارة إلى التعقيد.

النماذج الحسابية

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

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

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

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

حتى لو لم يكن نموذج الحساب هذا عمليًا حاليًا ، فإن له أهمية نظرية ، لا سيما فيما يتعلق بمشكلة P = NP ، التي تسأل عما إذا كانت فئات التعقيد الناتجة عن استخدام "وقت متعدد الحدود" و "وقت متعدد الحدود غير حتمي" على الأقل الحدود هي نفسها. على جهاز كمبيوتر محدد ، تتطلب محاكاة خوارزمية NP "وقتًا أسيًا". إذا كان من الممكن حل مهمة في وقت كثير الحدود على نظام غير حتمي ، فإنها تنتمي إلى فئة صعوبة NP. إذا كانت هناك مشكلة في NP وليست أسهل من أي مشكلة NP أخرى ، فيُقال إنها مكتملة NP. مشكلة الحقيبة ، مشكلة البائع المتجول ، ومشكلة الرضا المنطقية كلها مشاكل اندماجية كاملة NP. الخوارزمية الأكثر شهرة لها تعقيد أسي لكل هذه المشاكل. إذا كان من الممكن حل أي من هذه المشكلات في وقت متعدد الحدود على آلة حتمية ، فيمكن حل جميع مشكلات NP في وقت متعدد الحدود أيضًا ، وسيتم إنشاء P = NP. اعتبارًا من عام 2017 ، يُفترض على نطاق واسع أن P NP ، مما يعني أن أسوأ حالات مشاكل NP يصعب حلها بشكل أساسي ، أي أنها تستغرق وقتًا أطول بكثير من أي فترة زمنية ممكنة (عقود) نظرًا لأطوال المدخلات المثيرة للاهتمام.

الحوسبة المتوازية والموزعة

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

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

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

حساب الكم

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

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

تعقيد المشكلة (الحدود الدنيا)

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

نتيجة لذلك ، فإن أي تعقيد معطى في تدوين O الكبير يمثل تعقيدًا لكل من الخوارزمية والمشكلة المصاحبة.

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

لحل معظم المشكلات ، يجب قراءة جميع بيانات الإدخال ، الأمر الذي يستغرق وقتًا يتناسب مع حجم البيانات. نتيجة لذلك ، فإن مثل هذه المشكلات لها على الأقل تعقيد خطي ، أو في تدوين أوميغا الكبير ، تعقيد Ω (n).

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

عدد المقارنات المطلوبة لخوارزمية الفرز له حد سفلي غير خطي لـ Ω (nlogn). نتيجة لذلك ، فإن أفضل خوارزميات الفرز هي الأكثر كفاءة لأن تعقيدها هو O (nlogn). حقيقة أن هناك ن! طرق تنظيم ن الأشياء تؤدي إلى هذا الحد الأدنى. لأن كل مقارنة تقسم هذه المجموعة من n! الطلبات إلى قطعتين ، يجب أن يكون عدد المقارنات N المطلوبة للتمييز بين جميع الطلبات 2N> n! ، مما يعني ضمنيًا O (nlogn) بواسطة صيغة Stirling.

يعد تقليل المشكلة إلى مشكلة أخرى استراتيجية شائعة للحصول على قيود تعقيد أقل.

تطوير الخوارزمية

يعد تقييم تعقيد الخوارزمية عنصرًا مهمًا في عملية التصميم لأنه يوفر معلومات مفيدة حول الأداء المتوقع.

من سوء الفهم المتكرر أنه نتيجة لقانون مور ، الذي يتنبأ بالنمو الأسي لقوة الكمبيوتر الحديثة ، فإن تقييم تعقيد الخوارزميات سيصبح أقل أهمية. هذا غير صحيح لأن الطاقة المتزايدة تسمح بمعالجة كميات هائلة من البيانات (البيانات الضخمة). على سبيل المثال ، يجب أن تعمل أي خوارزمية بشكل جيد في أقل من ثانية عند الترتيب الأبجدي لقائمة من بضع مئات من الإدخالات ، مثل ببليوغرافيا الكتاب. من ناحية أخرى ، بالنسبة إلى مليون إدخال (على سبيل المثال ، أرقام هواتف مدينة كبيرة) ، يجب أن تقوم الخوارزميات الأساسية التي تتطلب مقارنات O (n2) بإجراء تريليون مقارنة ، والتي قد تستغرق ثلاث ساعات بسرعة 10 مليون مقارنة في الثانية. من ناحية أخرى ، لا يتطلب الفرز السريع والدمج سوى مقارنات nlogn (مثل تعقيد الحالة المتوسطة للحالة الأولى ، كأسوأ حالة تعقيد للأخيرة). ينتج عن هذا حوالي 30,000,000 مقارنات لـ n = 1,000,000 ، الأمر الذي سيستغرق 3 ثوانٍ فقط عند 10 مليون مقارنة في الثانية.

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