التعقيد الحسابي

في علم الحاسوب ، يُعرَّف التعقيد الحسابي ، أو ببساطة تعقيد الخوارزمية، بأنه مقدار الموارد اللازمة لتشغيلها. ^{[ 1 ]} ويُركَّز بشكل خاص على وقت الحساب (الذي يُقاس عادةً بعدد العمليات الأساسية المطلوبة) ومتطلبات تخزين الذاكرة . أما تعقيد المسألة، فهو تعقيد أفضل الخوارزميات التي تُتيح حلها.

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

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

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

يُعرَّف تعقيد الحالة الأسوأ بأنه الحد الأقصى للتعقيد لجميع المدخلات ذات الحجم n ، بينما يُعرَّف تعقيد الحالة المتوسطة بأنه متوسط ​​التعقيد لجميع المدخلات ذات الحجم n (وهذا منطقي، لأن عدد المدخلات الممكنة لحجم معين محدود). عمومًا، عند استخدام مصطلح "التعقيد" دون تحديده بدقة، يُقصد به تعقيد الحالة الأسوأ.

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

لهذه الأسباب، يُركز عادةً على سلوك التعقيد عند قيم n الكبيرة ، أي على سلوكه التقاربي عندما تؤول n إلى اللانهاية. ولذلك، يُعبَّر عن التعقيد عمومًا باستخدام ترميز Big O.

على سبيل المثال، تبلغ تعقيد الخوارزمية المعتادة لضرب الأعداد الصحيحة 10 ...${\displaystyle O(n^{2});}$هذا يعني وجود ثابت${\displaystyle c_{u}}$بحيث يمكن إجراء عملية ضرب عددين صحيحين لا يزيد عدد أرقامهما عن n في وقت أقل من${\displaystyle c_{u}n^{2}.}$هذا الحد دقيق بمعنى أن تعقيد الحالة الأسوأ وتعقيد الحالة المتوسطة هما${\displaystyle \Omega (n^{2}),}$وهذا يعني أن هناك أيضًا ثابتًا${\displaystyle c_{l}}$بحيث تكون هذه التعقيدات أكبر من${\displaystyle c_{l}n^{2}.}$لا يظهر الأساس في هذه التعقيدات، لأن تغيير الأساس لا يغير سوى الثوابت .${\displaystyle c_{u}}$و${\displaystyle c_{l}.}$

يعتمد تقييم التعقيد على اختيار نموذج الحوسبة ، والذي يتضمن تحديد العمليات الأساسية التي تُجرى في وحدة زمنية. عندما لا يُحدد نموذج الحوسبة صراحةً، يُفترض ضمنيًا أنه آلة تورينج متعددة الأشرطة ، نظرًا لأن العديد من نماذج الحوسبة الأكثر واقعية، مثل آلات الوصول العشوائي، تُكافئها تقاربًا في معظم المسائل. ويُستثنى من ذلك المسائل الصعبة والمحددة جدًا، مثل ضرب الأعداد الصحيحة في زمن معين.${\displaystyle O(n\log n),}$أن التعريف الصريح لنموذج الحساب مطلوب للإثباتات.

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

ويترتب على ذلك أن كل تعقيد لخوارزمية يتم التعبير عنها باستخدام ترميز Big O ، هو أيضًا حد أعلى لتعقيد المشكلة المقابلة.

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

لحل معظم المشكلات، من الضروري قراءة جميع بيانات الإدخال، وهو ما يتطلب عادةً وقتًا يتناسب مع حجم البيانات. وبالتالي، فإن تعقيد هذه المشكلات يكون خطيًا على الأقل ، أي باستخدام ترميز أوميغا الكبير ، يكون التعقيد${\displaystyle \Omega (n).}$

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

حد أدنى غير خطي لـ${\displaystyle \Omega (n\log n)}$يُعرف هذا بـ عدد المقارنات اللازمة لخوارزمية الفرز . وبالتالي، فإن أفضل خوارزميات الفرز هي خوارزميات مثالية تقاربياً، لأن تعقيدها${\displaystyle O(n\log n).}$ينتج هذا الحد الأدنى من حقيقة وجود n ! طريقة لترتيب n عنصرًا. وبما أن كل مقارنة تقسم هذه المجموعة المكونة من n ! ترتيبًا إلى جزأين ، فإن عدد المقارنات N اللازمة لتمييز جميع الترتيبات يجب أن يكون صحيحًا.${\displaystyle 2^{N}>n!,}$وهذا يعني${\displaystyle N=\Omega (n\log n),}$باستخدام صيغة ستيرلينغ .

تتمثل إحدى الطرق القياسية لإثبات الحدود الدنيا لتعقيد المسائل في اختزال المسألة إلى مسألة أخرى. بتعبير أدق، لنفترض أنه يمكن ترميز مسألة A ذات حجم n في مسألة فرعية بحجم f ( n ) من مسألة B ، وأن تعقيد A هو${\displaystyle \Omega (g(n)).}$دون الإخلال بعمومية المسألة، يمكن افتراض أن الدالة f تتزايد مع n ولها دالة عكسية h . عندئذٍ، يكون تعقيد المسألة B هو${\displaystyle \Omega (g(h(n))).}$هذه هي الطريقة المستخدمة لإثبات أنه إذا كانت P ≠ NP (وهي تخمين لم يُحل بعد)، فإن تعقيد كل مسألة كاملة من فئة NP هو${\displaystyle \Omega (n^{k}),}$لكل عدد صحيح موجب k .

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

من المفاهيم الخاطئة الشائعة أن تقييم تعقيد الخوارزميات سيصبح أقل أهمية نتيجة لقانون مور ، الذي ينص على النمو الأسي لقدرة الحواسيب الحديثة . هذا غير صحيح، لأن هذه الزيادة في القدرة تسمح بالتعامل مع كميات هائلة من البيانات ( البيانات الضخمة ). على سبيل المثال، عند الرغبة في فرز قائمة تضم بضع مئات من المدخلات أبجديًا، مثل قائمة مراجع كتاب، ينبغي لأي خوارزمية أن تعمل بكفاءة في أقل من ثانية. من ناحية أخرى، بالنسبة لقائمة تضم مليون مدخل (أرقام هواتف مدينة كبيرة، على سبيل المثال)، فإن الخوارزميات الأساسية التي تتطلب${\displaystyle O(n^{2})}$سيتطلب إجراء المقارنات تريليون مقارنة، وهو ما سيستغرق حوالي ثلاث ساعات بسرعة 10 ملايين مقارنة في الثانية. من ناحية أخرى، لا تتطلب خوارزميات الفرز السريع والفرز بالدمج سوى${\displaystyle n\log _{2}n}$المقارنات (كمتوسط ​​تعقيد الحالة الأولى، وكأسوأ تعقيد الحالة الثانية). بالنسبة لـ n = 1,000,000 ، ينتج عن ذلك ما يقارب 30,000,000 مقارنة، وهو ما يستغرق 3 ثوانٍ فقط بمعدل 10 ملايين مقارنة في الثانية.

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

• التعقيد الحسابي للعمليات الرياضية
• قائمة تعقيدات مشكلة ساعي البريد الصيني
• نظرية ماستر (تحليل الخوارزميات)

• أرورا، سانجيف ؛ باراك، بواز (2009)، التعقيد الحسابي: منهج حديث ، كامبريدج ، ISBN 978-0-521-42426-4، Zbl 1193.68112 
• كالود، كريستيان (1988)، نظريات التعقيد الحسابي ، إلسيفير ، ص  487، ISBN 9780444703569
• دو، دينغ تشو؛ كو كير-I (2000)، نظرية التعقيد الحسابي ، جون وايلي وأولاده ، ISBN 978-0-471-34506-0ISSN 0167-5060​ 
• غاري، مايكل ر .؛ جونسون، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، سلسلة كتب في العلوم الرياضية (  الطبعة الأولى)، نيويورك: دبليو إتش فريمان وشركاه ، ISBN 9780716710455، MR 0519066 ، OCLC 247570676  
• جولدرايش، أوديد (2008)، التعقيد الحسابي: منظور مفاهيمي ، مطبعة جامعة كامبريدج
• فان ليوين، يان ، محرر (1990)، دليل علوم الحاسوب النظرية (المجلد أ): الخوارزميات والتعقيد ، مطبعة معهد ماساتشوستس للتكنولوجيا ، رقم ISBN 978-0-444-88071-0
• باباديميتريو، كريستوس (1994)، التعقيد الحسابي (  الطبعة الأولى)، أديسون ويسلي، رقم ISBN 0-201-53082-1
• سيبسر، مايكل (2006)، مقدمة في نظرية الحوسبة (  الطبعة الثانية)، الولايات المتحدة الأمريكية: تومسون كورس تكنولوجي ، رقم ISBN 0-534-95097-3