تعقيد الخطة

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

بما أن زمن تشغيل الخوارزمية قد يختلف باختلاف المدخلات ذات الحجم نفسه، يُؤخذ عادةً في الاعتبار تعقيد الوقت في أسوأ الحالات ، وهو أقصى وقت مطلوب لمدخلات ذات حجم مُحدد. أما تعقيد الحالة المتوسطة ، وهو متوسط ​​الوقت المستغرق لمدخلات ذات حجم مُحدد (وهذا منطقي لأن عدد المدخلات الممكنة ذات الحجم المُحدد محدود)، فهو أقل شيوعًا، ويُحدد عادةً بشكل صريح. في كلتا الحالتين، يُعبَّر عن تعقيد الوقت كدالة لحجم المدخل. ^{[ 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)}$--i.e., if the word ${\displaystyle w}$ comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.

An algorithm is said to run in polylogarithmic time if its time ${\displaystyle T(n)}$ is ${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$ for some constant ${\displaystyle k}$. Another way to write this is ${\displaystyle O(\log ^{k}n)}$.

For example, matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine,^[7] and a graph can be determined to be planar in a fully dynamic way in ${\displaystyle O(\log ^{3}n)}$ time per insert/delete operation.^[8]

An algorithm is said to run in sub-linear time (often spelled sublinear time) if ${\displaystyle T(n)=o(n)}$. In particular this includes algorithms with the time complexities defined above.

The specific term sublinear time algorithm commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to approximately infer properties of the entire instance.^[9] This type of sublinear time algorithm is closely related to property testing and statistics.

Other settings where algorithms can run in sublinear time include:

• Parallel algorithms that have linear or greater total work (allowing them to read the entire input), but sub-linear depth.
• Algorithms that have guaranteed assumptions on the input structure. An important example are operations on data structures, e.g. binary search in a sorted array.
• Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in ${\displaystyle O(\log(n))}$ time using a variant of binary search). A closely related notion is that of Local Computation Algorithms (LCA) where the algorithm receives a large input and queries to local information about some valid large output.^[10]

An algorithm is said to take linear time, or ${\displaystyle O(n)}$ time, if its time complexity is ${\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})}$وهو خوارزمية ذات وقت متعدد الحدود.
• يمكن إجراء جميع العمليات الحسابية الأساسية (الجمع والطرح والضرب والقسمة والمقارنة) في وقت متعدد الحدود.
• يمكن إيجاد أقصى عدد من المطابقات في الرسوم البيانية في وقت متعدد الحدود. في بعض السياقات، وخاصة في مجال التحسين ، يتم التمييز بين الخوارزميات ذات الوقت متعدد الحدود القوي والخوارزميات ذات الوقت متعدد الحدود الضعيف .

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

An algorithm is defined to take superpolynomial time if ${\displaystyle T(n)}$ is not bounded above by any polynomial; that is, if ${\displaystyle T(n)\not \in O(n^{c})}$ for every positive integer ${\displaystyle c}$.

For example, an algorithm that runs for ${\displaystyle 2^{n}}$ steps on an input of size ${\displaystyle n}$ requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the Adleman–Pomerance–Rumely primality test runs for ${\displaystyle n^{O(\log \log n)}}$ time on ${\displaystyle n}$-bit inputs; this grows faster than any polynomial for large enough ${\displaystyle n}$, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside the complexity classP. Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, it is unknown whether NP-complete problems require superpolynomial time.

Quasi-polynomial time algorithms are algorithms whose running time exhibits quasi-polynomial growth, a type of behavior that may be slower than polynomial time but yet is significantly faster than exponential time. The worst case running time of a quasi-polynomial time algorithm is ${\displaystyle 2^{O(\log ^{c}n)}}$ for some fixed ${\displaystyle c>0}$. When ${\displaystyle c=1}$ this gives polynomial time, and for ${\displaystyle c<1}$ it gives sub-linear time.

توجد بعض المسائل التي نعرف لها خوارزميات ذات زمن شبه متعدد الحدود، ولكن لا توجد خوارزمية ذات زمن متعدد الحدود معروفة. تنشأ هذه المسائل في خوارزميات التقريب؛ ومن الأمثلة الشهيرة مسألة شجرة شتاينر الموجهة ، والتي توجد لها خوارزمية تقريب ذات زمن شبه متعدد الحدود تحقق عامل تقريب قدره${\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
• تعقيد المساحة