تعقيد حسابي

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

الموارد

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

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