تعقيد الخطة

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

بما أن زمن تشغيل الخوارزمية قد يختلف باختلاف المدخلات ذات الحجم نفسه، يُؤخذ عادةً في الاعتبار تعقيد الوقت في أسوأ الحالات ، وهو أقصى وقت مطلوب لمدخلات ذات حجم مُحدد. أما تعقيد الحالة المتوسطة ، وهو متوسط ​​الوقت المستغرق لمدخلات ذات حجم مُحدد (وهذا منطقي لأن عدد المدخلات الممكنة ذات الحجم المُحدد محدود)، فهو أقل شيوعًا، ويُحدد عادةً بشكل صريح. في كلتا الحالتين، يُعبَّر عن تعقيد الوقت كدالة لحجم المدخل. ^{[ 1 ] : 226.} ولأن حساب هذه الدالة بدقة أمر صعب عمومًا، ولأن زمن التشغيل للمدخلات الصغيرة لا يكون ذا أهمية عادةً، يُركز عادةً على سلوك التعقيد مع ازدياد حجم المدخل، أي السلوك التقاربي للتعقيد. لذلك، يُعبَّر عن تعقيد الوقت عادةً باستخدام ترميز Big O ، وعادةً ما يكون${\displaystyle O(n)}$،${\displaystyle O(n\log n)}$،${\displaystyle O(n^{\alpha })}$،${\displaystyle O(2^{n})}$إلخ، حيث${\displaystyle n}$هو الحجم بوحدات البت اللازمة لتمثيل المدخلات.

تُصنّف التعقيدات الخوارزمية وفقًا لنوع الدالة التي تظهر في ترميز Big O. على سبيل المثال، خوارزمية ذات تعقيد زمني${\displaystyle O(n)}$هي خوارزمية ذات زمن خطي وخوارزمية ذات تعقيد زمني${\displaystyle O(n^{\alpha })}$لبعض الثوابت${\displaystyle \alpha >0}$هي خوارزمية ذات وقت متعدد الحدود .

يلخص الجدول التالي بعض فئات التعقيدات الزمنية الشائعة. في الجدول،${\displaystyle {\text{poly}}(x)=x^{O(1)}}$أي، متعددة الحدود في${\displaystyle x}$.

اسم	فئة التعقيد	تعقيد الخطة${\displaystyle O(n)}$	أمثلة على أوقات التشغيل	أمثلة على الخوارزميات
زمن ثابت		${\displaystyle O(1)}$	10	إيجاد القيمة الوسيطة في مصفوفة أرقام مرتبة. حساب${\displaystyle (-1)^{n}}$.
زمن أكرمان العكسي		${\displaystyle O{\bigl (}\alpha (n){\bigr )}}$		الوقت المستهلك لكل عملية باستخدام مجموعة منفصلة
الوقت اللوغاريتمي المتكرر		${\displaystyle O(\log ^{*}n)}$		تلوين موزّع للدورات
لوغاريتمي-لوغاريتمي		${\displaystyle O(\log \log n)}$		الوقت المستهلك لكل عملية باستخدام قائمة انتظار ذات أولوية محدودة [ 2 ]
الزمن اللوغاريتمي	DLOGTIME	${\displaystyle O(\log n)}$	${\displaystyle \log n}$،${\displaystyle \log(n^{2})}$	البحث الثنائي
الزمن متعدد اللوغاريتمات		${\displaystyle {\text{poly}}(\log n)}$	${\displaystyle (\log n)^{2}}$
القوة الكسرية		${\displaystyle O(n^{c})}$أين${\displaystyle 0<c<1}$	${\displaystyle {\sqrt {n}}}$،${\displaystyle n^{\frac {2}{3}}}$	البحث في نطاق شجرة k -d
الزمن الخطي		${\displaystyle O(n)}$	${\displaystyle n}$،${\displaystyle 2n+5}$	إيجاد أصغر أو أكبر عنصر في مصفوفة غير مرتبة . خوارزمية كادان . البحث الخطي .
"n log-star n" الزمن		${\displaystyle O(n\log ^{*}n)}$		خوارزمية تثليث المضلعات لسيدل .
الزمن الخطي		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$،${\displaystyle \log n!}$	أسرع طريقة ممكنة لفرز المقارنات . تحويل فورييه السريع .
الزمن شبه الخطي		${\displaystyle n{\text{poly}}(\log n)}$	${\displaystyle n\log ^{2}n}$	تقييم متعدد النقاط لكثيرات الحدود
الزمن التربيعي		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	فرز الفقاعات . فرز الإدراج . الالتفاف المباشر
الزمن المكعبي		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	عملية ضرب بسيطة للعدد اثنين${\displaystyle n\times n}$المصفوفات. حساب الارتباط الجزئي .
زمن متعدد الحدود	P	${\displaystyle 2^{O(\log n)}={\text{poly}}(n)}$	${\displaystyle n^{2}+n}$،${\displaystyle n^{10}}$	خوارزمية كارماركار للبرمجة الخطية . اختبار أولية AKS [ 3 ] [ 4 ]
زمن شبه متعدد الحدود	كيو بي	${\displaystyle 2^{{\text{poly}}(\log n)}}$	${\displaystyle n^{\log \log n}}$،${\displaystyle n^{\log n}}$	الأكثر شهرة${\displaystyle O(\log ^{2}n)}$خوارزمية تقريبية لمسألة شجرة شتاينر الموجهة ، وأفضل خوارزمية معروفة لحل لعبة التكافؤ ، [ 5 ] وأفضل خوارزمية معروفة لتماثل الرسوم البيانية
الزمن دون الأسي (التعريف الأول)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$للجميع${\displaystyle \epsilon >0}$		يحتوي على BPP ما لم يكن EXPTIME (انظر أدناه) يساوي MA . [ 6 ]
الزمن دون الأسي (التعريف الثاني)		${\displaystyle 2^{o(n)}}$	${\displaystyle 2^{\sqrt[{3}]{n}}}$	أفضل خوارزمية كلاسيكية لتحليل الأعداد الصحيحة إلى عواملها الأولية أفضل خوارزمية سابقة لتماثل الرسوم البيانية
الزمن الأسي (مع الأس الخطي)	هـ	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$،${\displaystyle 10^{n}}$	حل مسألة البائع المتجول باستخدام البرمجة الديناميكية
زمن العاملي		${\displaystyle O(n)!=2^{O(n\log n)}}$	${\displaystyle n!,n^{n},2^{n\log n}}$	حل مشكلة البائع المتجول باستخدام البحث الشامل
الزمن الأسي	وقت الخبرة	${\displaystyle 2^{{\text{poly}}(n)}}$	${\displaystyle 2^{n}}$،${\displaystyle 2^{n^{2}}}$	حل مسألة ضرب سلاسل المصفوفات باستخدام البحث الشامل . إيجاد استراتيجية رابحة في الشطرنج أو الداما أو لعبة غو باستخدام قاعدة "كو" اليابانية.${\displaystyle n\times n}$سبورة.
زمن أسي مزدوج	2-EXPTIME	${\displaystyle 2^{2^{{\text{poly}}(n)}}}$	${\displaystyle 2^{2^{n}}}$	تحديد صحة عبارة معينة في حساب بريسبرغر

يُطلق على الخوارزمية اسم الخوارزمية ذات الوقت الثابت (والتي غالبًا ما يتم تمثيلها بـ${\displaystyle O(1)}$الوقت) عندما تكون دالة تعقيدها${\displaystyle T(n)}$يُحدَّد وقت التنفيذ بقيمة ثابتة لا تتغير بتغير حجم المدخلات. وهذا يعني أن وقت التنفيذ يظل ثابتًا بغض النظر عن حجم البيانات المُعالَجة. على سبيل المثال، يُعد الوصول إلى عنصر مُحدد في مصفوفة عمليةً ذات وقت ثابت، إذ لا تتطلب سوى عملية واحدة لتحديد موقع ذلك العنصر.

في المقابل، لا يُعدّ تحديد القيمة الدنيا في مصفوفة غير مرتبة عمليةً ذات زمن ثابت؛ إذ يتطلب فحص كل عنصر ، مما ينتج عنه تعقيد زمني خطي، أو${\displaystyle O(n)}$ومع ذلك، إذا كان عدد العناصر معروفًا وثابتًا، فلا يزال من الممكن اعتبار بعض المهام ذات وقت ثابت.

من المهم الإشارة إلى أن مصطلح "الوقت الثابت" لا يعني أن وقت التشغيل يجب أن يكون مستقلاً تماماً عن حجم المشكلة؛ بل يجب أن يكون له حد أعلى ثابت بغض النظر عن حجم المدخلات. على سبيل المثال، مهمة تتضمن تبديل قيم${\displaystyle a}$و${\displaystyle b}$لضمان${\displaystyle a\leq b}$يُصنف هذا النوع على أنه ذو زمن ثابت، حتى وإن كان زمن التنفيذ قد يختلف تبعًا لما إذا كان الشرط قد تحقق بالفعل. يكمن جوهر الأمر في وجود ثابت.${\displaystyle t}$بحيث لا يتجاوز الوقت المستغرق أبداً${\displaystyle t}$بغض النظر عن قيم الإدخال.

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

يقال إن الخوارزمية تستغرق وقتًا لوغاريتميًا عندما${\displaystyle T(n)=O(\log n)}$. منذ${\displaystyle \log _{a}n}$و${\displaystyle \log _{b}n}$ترتبط هذه المتغيرات بمعامل ثابت ، وهذا المعامل غير ذي صلة بتصنيف Big O، والاستخدام القياسي لخوارزميات الوقت اللوغاريتمي هو${\displaystyle O(\log n)}$بغض النظر عن أساس اللوغاريتم الظاهر في تعبير${\displaystyle T}$.

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

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

يُعد البحث في القاموس مثالاً على الزمن اللوغاريتمي. لنفترض وجود قاموس .${\displaystyle D}$والذي يحتوي${\displaystyle n}$المدخلات مرتبة أبجديًا . نفترض أنه، بالنسبة لـ${\displaystyle 1\leq k\leq n}$، يمكن الوصول إلى${\displaystyle k}$المدخل رقم n من القاموس في زمن ثابت. ليكن${\displaystyle D(k)}$يشير هذا إلى${\displaystyle k}$المدخل رقم -th. في ظل هذه الفرضيات، يتم إجراء اختبار لمعرفة ما إذا كانت الكلمة${\displaystyle w}$يمكن إنجاز ما هو موجود في القاموس في وقت لوغاريتمي: ضع في اعتبارك${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$، أين${\displaystyle \lfloor \;\rfloor }$يرمز إلى دالة الجزء الصحيح . إذا${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$أي بمعنى الكلمة${\displaystyle w}$إذا كان النص في منتصف القاموس تمامًا، فقد انتهينا. وإلا، إذا${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$أي، إذا كانت الكلمة${\displaystyle w}$إذا كانت الكلمة تقع أبجديًا قبل الكلمة الوسطى في القاموس، نواصل البحث بنفس الطريقة في النصف الأيسر (أي الأبكر) من القاموس، ثم نكرر العملية حتى نجد الكلمة الصحيحة. أما إذا كانت الكلمة تقع بعد الكلمة الوسطى، فنواصل البحث بنفس الطريقة في النصف الأيمن من القاموس. تشبه هذه الخوارزمية الطريقة المستخدمة عادةً للعثور على مدخل في قاموس ورقي. ونتيجةً لذلك، يتقلص نطاق البحث داخل القاموس كلما اقتربت الخوارزمية من الكلمة المستهدفة.

يُقال إن الخوارزمية تعمل في وقت متعدد اللوغاريتمات إذا كان وقتها${\displaystyle T(n)}$يكون${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$لبعض الثوابت${\displaystyle k}$طريقة أخرى لكتابة هذا هي${\displaystyle O(\log ^{k}n)}$.

على سبيل المثال، يمكن حل مسألة ترتيب سلسلة المصفوفات في وقت متعدد اللوغاريتمات على جهاز وصول عشوائي متوازي ، ^{[ 7 ]} ويمكن تحديد ما إذا كان الرسم البياني مستويًا بطريقة ديناميكية بالكامل في${\displaystyle O(\log ^{3}n)}$الوقت اللازم لكل عملية إدراج/حذف. ^{[ 8 ]}

يُقال إن الخوارزمية تعمل في وقت دون خطي (غالباً ما تُكتب دون خطي ) إذا${\displaystyle T(n)=o(n)}$ويشمل ذلك على وجه الخصوص الخوارزميات ذات التعقيدات الزمنية المحددة أعلاه.

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

تشمل الإعدادات الأخرى التي يمكن فيها تشغيل الخوارزميات في وقت أقل من الخطي ما يلي:

• الخوارزميات المتوازية التي لها عمل إجمالي خطي أو أكبر (مما يسمح لها بقراءة المدخلات بأكملها)، ولكن بعمق أقل من الخطي .
• الخوارزميات التي تعتمد على افتراضات مضمونة بشأن بنية المدخلات. ومن الأمثلة المهمة على ذلك العمليات على هياكل البيانات ، مثل البحث الثنائي في مصفوفة مرتبة.
• يمكن حل الخوارزميات التي تبحث عن بنية محلية في المدخلات، على سبيل المثال إيجاد الحد الأدنى المحلي في مصفوفة أحادية البعد (باستخدام لغة البرمجة .${\displaystyle O(\log(n))}$(باستخدام صيغة معدلة من البحث الثنائي). وهناك مفهوم وثيق الصلة وهو مفهوم خوارزميات الحساب المحلي (LCA) حيث تتلقى الخوارزمية مدخلات كبيرة وتستعلم عن معلومات محلية حول بعض المخرجات الكبيرة الصالحة. ^{[ 10 ]}

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

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

يُقال إن الخوارزمية تعمل في وقت شبه خطي (يُشار إليه أيضًا بالوقت اللوغاريتمي الخطي ) إذا${\displaystyle T(n)=O(n\log ^{k}n)}$لبعض الثوابت الموجبة${\displaystyle k}$; ^{[ 11 ]} الوقت الخطي اللوغاريتمي هو الحالة${\displaystyle k=1}$[ ^{12 ]} باستخدام ترميز O الناعم، ^تكون هذه الخوارزميات${\displaystyle {\tilde {O}}(n)}$تُعتبر الخوارزميات شبه الخطية أيضًا${\displaystyle O(n^{1+\varepsilon })}$لكل ثابت${\displaystyle \varepsilon >0}$وبالتالي تعمل بشكل أسرع من أي خوارزمية ذات وقت متعدد الحدود يتضمن حدها الزمني حدًا${\displaystyle n^{c}}$لأي${\displaystyle c>1}$.

تشمل الخوارزميات التي تعمل في وقت شبه خطي ما يلي:

• فرز الدمج في مكانه ،${\displaystyle O(n\log ^{2}n)}$
• الفرز السريع ،${\displaystyle O(n\log n)}$، في نسختها العشوائية، لها وقت تشغيل هو${\displaystyle O(n\log n)}$في حالة توقع أسوأ حالة إدخال. نسختها غير العشوائية لها${\displaystyle O(n\log n)}$وقت التشغيل فقط عند النظر في تعقيد الحالة المتوسطة.
• فرز الكومة ،${\displaystyle O(n\log n)}$، فرز الدمج ، فرز الإدخال ، فرز الشجرة الثنائية، الفرز السلس ، فرز الصبر ، إلخ. في أسوأ الحالات
• تحويلات فورييه السريعة ،${\displaystyle O(n\log n)}$
• حساب مصفوفة مونجي ،${\displaystyle O(n\log n)}$
• خوارزمية Schönhage-Strassen للضرب ،${\displaystyle O(n\log n\log \log n)}$

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

تتطلب عمليات فرز المقارنة على الأقل${\displaystyle \Omega (n\log n)}$المقارنات في أسوأ الحالات لأن${\displaystyle \log(n!)=\Theta (n\log n)}$، بتقريب ستيرلنغ . كما أنها تنشأ في كثير من الأحيان من علاقة التكرار${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$.

يُقال إن الخوارزمية تعمل في زمن أقل من التربيعي إذا${\displaystyle T(n)=o(n^{2})}$.

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

يُقال إن الخوارزمية ذات زمن متعدد الحدود إذا كان زمن تشغيلها محدودًا من الأعلى بتعبير متعدد الحدود في حجم مدخلات الخوارزمية، أي${\displaystyle 1=T(n)=O(n^{k})}$لبعض الثوابت الموجبة${\displaystyle k}$[ ^{1 ] [ 13 ]} تنتمي المسائل التي يوجد لها خوارزمية حتمية متعددة الحدود إلى فئة التعقيد P ، وهي فئة محورية في مجال نظرية التعقيد الحسابي . تنص أطروحة كوبام على أن الوقت متعدد الحدود مرادف لـ "قابل للمعالجة" أو "ممكن" أو "فعال" أو "سريع" ^{. [ 14 ]}

بعض الأمثلة على الخوارزميات ذات الوقت متعدد الحدود:

• خوارزمية فرز الاختيار على${\displaystyle n}$أداء الأعداد الصحيحة${\displaystyle An^{2}}$عمليات لبعض الثوابت${\displaystyle A}$وهكذا يسير الأمر في الوقت المناسب${\displaystyle O(n^{2})}$وهو خوارزمية ذات وقت متعدد الحدود.
• يمكن إجراء جميع العمليات الحسابية الأساسية (الجمع والطرح والضرب والقسمة والمقارنة) في وقت متعدد الحدود.
• يمكن إيجاد أقصى عدد من المطابقات في الرسوم البيانية في وقت متعدد الحدود. في بعض السياقات، وخاصة في مجال التحسين ، يتم التمييز بين الخوارزميات ذات الوقت متعدد الحدود القوي والخوارزميات ذات الوقت متعدد الحدود الضعيف .

لا يكون هذان المفهومان ذي صلة إلا إذا كانت مدخلات الخوارزميات تتكون من أعداد صحيحة.

يُعرَّف الخوارزمية بأنها تستغرق وقتًا فائقًا متعدد الحدود إذا${\displaystyle T(n)}$لا يحدها من الأعلى أي متعدد حدود؛ أي إذا${\displaystyle T(n)\not \in O(n^{c})}$لكل عدد صحيح موجب${\displaystyle c}$.

على سبيل المثال، خوارزمية تعمل لمدة${\displaystyle 2^{n}}$خطوات على مدخل بحجم${\displaystyle n}$يتطلب وقتاً فائقاً متعدد الحدود (وبشكل أكثر تحديداً، وقتاً أسياً).

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

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

الخوارزميات ذات الوقت شبه متعدد الحدود هي خوارزميات يُظهر وقت تشغيلها نموًا شبه متعدد الحدود ، وهو نمط سلوك قد يكون أبطأ من الوقت متعدد الحدود ولكنه أسرع بكثير من الوقت الأسي . أسوأ حالة لوقت تشغيل خوارزمية ذات وقت شبه متعدد الحدود هي${\displaystyle 2^{O(\log ^{c}n)}}$لبعض الثوابت${\displaystyle c>0}$. متى${\displaystyle c=1}$وهذا يعطي وقتاً متعدد الحدود، و لـ${\displaystyle c<1}$إنه يعطي زمنًا دون الخطي.

توجد بعض المسائل التي نعرف لها خوارزميات ذات زمن شبه متعدد الحدود، ولكن لا توجد خوارزمية ذات زمن متعدد الحدود معروفة. تنشأ هذه المسائل في خوارزميات التقريب؛ ومن الأمثلة الشهيرة مسألة شجرة شتاينر الموجهة ، والتي توجد لها خوارزمية تقريب ذات زمن شبه متعدد الحدود تحقق عامل تقريب قدره${\displaystyle O(\log ^{3}n)}$(${\displaystyle n}$(حيث يمثل عدد الرؤوس)، لكن إثبات وجود خوارزمية زمنية متعددة الحدود كهذه يمثل مشكلة مفتوحة.

تتضمن مسائل حسابية أخرى ذات حلول شبه متعددة الحدود، ولكن ليس لها حلول متعددة الحدود معروفة، مسألة الزمرة المزروعة ، حيث يتمثل الهدف في إيجاد زمرة كبيرة في اتحاد زمرة ورسم بياني عشوائي . على الرغم من إمكانية حلها شبه متعدد الحدود، فقد تم التكهن بأن مسألة الزمرة المزروعة ليس لها حل متعدد الحدود؛ وقد استُخدم هذا التكهن كفرضية صعوبة حسابية لإثبات صعوبة العديد من المسائل الأخرى في نظرية الألعاب الحسابية ، واختبار الخصائص ، والتعلم الآلي . ^{[ 15 ]}

تتألف فئة التعقيد QP من جميع المسائل التي لها خوارزميات ذات وقت شبه متعدد الحدود. ويمكن تعريفها بدلالة DTIME على النحو التالي. ^{[ 16 ]}

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}$

يُستخدم مصطلح " الزمن شبه الأسي" للتعبير عن أن زمن تشغيل خوارزمية ما قد ينمو بوتيرة أسرع من أي دالة متعددة الحدود، ولكنه يظل أصغر بكثير من الزمن الأسي. وبهذا المعنى، تُعدّ المسائل التي تتطلب خوارزميات ذات زمن شبه أسي أسهل حلاً من تلك التي تتطلب خوارزميات ذات زمن أسي فقط. لا يوجد تعريف دقيق لمصطلح "شبه أسي" متفق عليه عمومًا ^{[ 18 ]،} إلا أن التعريفين الأكثر شيوعًا مذكوران أدناه.

يُقال إن الخوارزمية تعمل في زمن أسي ، إذا${\displaystyle T(n)}$يحدها من الأعلى:${\displaystyle 2^{{\text{poly}}(n)}}$، أين${\displaystyle {\text{poly}}(n)}$هي دالة متعددة الحدود في${\displaystyle n}$بصورة أدق، يكون وقت الخوارزمية أسيًا إذا${\displaystyle T(n)}$يحدها${\displaystyle O(2^{n^{k}})}$لبعض الثوابت${\displaystyle k}$تشكل المشكلات التي تقبل خوارزميات الوقت الأسي على آلة تورينج الحتمية فئة التعقيد المعروفة باسم EXP .

${\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}$

يُستخدم مصطلح الوقت الأسي أحيانًا للإشارة إلى الخوارزميات التي لديها${\displaystyle T(n)=2^{O(n)}}$، حيث يكون الأس على الأكثر دالة خطية لـ${\displaystyle n}$وهذا يؤدي إلى ظهور فئة التعقيد E.

${\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}$

يُقال إن الخوارزمية تعمل في زمن مضروب إذا${\displaystyle T(n)}$يتم تحديد الحد الأعلى بواسطة دالة المضروب${\displaystyle n!}$يُعدّ زمن العاملي مجموعة فرعية من الزمن الأسي (EXP) لأن${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$للجميع${\displaystyle \epsilon >0}$ومع ذلك، فهي ليست مجموعة فرعية من E.

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

يُقال إن الخوارزمية تعمل بزمن أسي مزدوج إذا${\displaystyle T(n)}$يحدها من الأعلى:${\displaystyle 2^{2^{{\text{poly}}(n)}}}$، أين${\displaystyle {\text{poly}}(n)}$هي دالة متعددة الحدود في${\displaystyle n}$تنتمي هذه الخوارزميات إلى فئة التعقيد 2-EXPTIME .

${\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}$

تشمل الخوارزميات المعروفة ذات الوقت الأسي المزدوج ما يلي:

• إجراءات اتخاذ القرار في حساب بريسبرغر
• حساب أساس غروبنر (في أسوأ الحالات ^{[ 27 ]} )
• تستغرق عملية إزالة الكميات على الحقول المغلقة الحقيقية وقتاً أسياً مزدوجاً على الأقل، ^{[ 28 ]} ويمكن إنجازها في هذا الوقت. ^{[ 29 ]}

• الترميز L
• تعقيد المساحة