نظرية التسريع

في نظرية التعقيد الحسابي ، تُعرف نظرية تسريع الأداء بأنها نظرية تُثبت ، بالنسبة لأي خوارزمية (من فئة معينة)، وجود خوارزمية أكثر كفاءة لحل نفس المشكلة. ^{[ 1 ]}

أمثلة:

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

• قانون أمدال ، وهو التسارع النظري في زمن استجابة تنفيذ مهمة ما عند عبء عمل ثابت يمكن توقعه من نظام تم تحسين موارده.