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

في نظرية التعقيد الحسابي ، يُعد التعقيد الحسابي التقاربي هو استخدام التحليل التقاربي لتقدير التعقيد الحسابي للخوارزميات والمسائل الحسابية ، ويرتبط عادةً باستخدام رمز O الكبير .

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

منذ الورقة البحثية الرائدة لعام 1965 التي نشرها جوريس هارتمانيس وريتشارد إي. ستيرنز ^{[ 1 ]} وكتاب مايكل غاري وديفيد إس. جونسون لعام 1979 حول اكتمال NP ، ^{[ 2 ]} أصبح مصطلح " التعقيد الحسابي " (للخوارزميات) شائع الاستخدام للإشارة إلى التعقيد الحسابي التقاربي.

علاوة على ذلك، ما لم يُنص على خلاف ذلك، يشير مصطلح "التعقيد الحسابي" عادةً إلى حد أعلى للتعقيد الحسابي التقاربي لخوارزمية أو مشكلة، والذي يُكتب عادةً باستخدام رمز Big O ، على سبيل المثال${\displaystyle O(n^{3}).}$هناك أنواع أخرى من تقديرات التعقيد الحسابي (التقاربي) وهي الحدود الدنيا ( رمز أوميغا الكبير ؛ على سبيل المثال، Ω( n )) والتقديرات التقاربية المحكمة، عندما تتطابق الحدود العليا والسفلى التقاربية (المكتوبة باستخدام " ثيتا الكبيرة "؛ على سبيل المثال، Θ( n log n )).

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

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

• خوارزمية مثالية تقاربياً