عرض مصدر تعقيد الوقت

في [[علم الحاسوب]]، يعتبر '''تعقيد الوقت''' هو '''التعقيد '''الحسابي الذي يقيس أو يقدر الوقت المستغرق لتشغيل [[خوارزمية]]. عادةً ما يتم تقدير تعقيد الوقت من خلال حساب عدد العمليات الأولية التي تقوم بها الخوارزمية، بافتراض أن العملية الأولية تستغرق وقتًا ثابتًا لأداءها. وبالتالي، فإن مقدار الوقت المستغرق وعدد العمليات الأولية التي تقوم بها الخوارزمية يختلفان على الأكثر [[تمثيل O الكبرى|بعامل ثابت]].

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

في كلتا الحالتين، يتم التعبير عن تعقيد الوقت بشكل عام [[دالة|كدالة]] لحجم المدخلات. {{صفحات مرجع|226}}{{صفحات مرجع|226}}<div class="cx-overlay"><div class="cx-spinner"></div></div>بما أن هذه الوظيفة يصعب بشكل عام حسابها بالضبط، ووقت التشغيل عادة لا يكون حرجًا بالنسبة إلى المدخلات الصغيرة، فإن أحدهما يركز عادة على سلوك التعقيد عندما يزيد حجم المدخلات؛ وهذا هو، على السلوك المقارب للتعقيد. لذلك، يتم التعبير عن تعقيد الوقت بشكل شائع باستخدام [[تمثيل O الكبرى|تدوين O الكبير]]، عادةً، إلخ، حيث n هو حجم الإدخال المقاس بعدد [[بت|البتات]] المطلوبة لتمثيله.<math>O(n),</math>
<math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math>[[بت]]

يتم تصنيف تعقيدات الخوارزمية بواسطة الدالة التي تظهر في تدوين O الكبير. على سبيل المثال، خوارزمية ذات تعقيد زمني هي ''خوارزمية زمنية خطية'' ، خوارزمية مع تعقيد زمني لبعض الثابت هي ''خوارزمية زمن متعددة الحدود'' .<math>O(n)</math>''''<math>O(n^\alpha)</math><math>\alpha \ge 1</math>''''

== جدول التعقيدات الزمنية الشائعة ==
يلخص الجدول التالي بعض فئات التعقيدات الزمنية الشائعة. في الجدول، poly (''x'') &nbsp;= ''x ''<sup>''O''</sup><sup> (1)</sup> ، أي كثيرات الحدود في ''x'' .&nbsp;''''<sup>''''</sup>''''
{| class="wikitable sortable" style="margin-bottom: 10px;"
! اسم 
! [[قسم تعقيد|فئة التعقيد]] 
!وقت التشغيل (''T'' (''n''))
! أمثلة على أوقات التشغيل 
! خوارزميات المثال
|-
| وقت ثابت 
| ''يا'' (1)
| 10 
| تحديد ما إذا كان عدد صحيح (يمثل في ثنائي) حتى أو فردي
|-
| [[دالة أكرمان|معكوس أكرمان]] الوقت
| ''O'' (''α'' (''n''))
| الوقت المستهلك لكل عملية باستخدام مجموعة [[هيكلة بيانات المجموعات المنفصلة|منفصلة]]
|-
| الوقت لوغاريتمي تكررت
| ''يا'' (سجل *&nbsp;''ن'')
| [[مسألة تلوين المخطط|التلوين الموزع للدورات]]
|-
| تسجيل-وغاريتمي 
| ''يا'' (سجل الدخول ''ن'')
|الوقت المستهلك لكل عملية باستخدام قائمة انتظار ذات أولوية محددة<ref>{{استشهاد بدورية محكمة|عنوان=Bounded ordered dictionaries in O(log log N) time and O(n) space|صحيفة=Information Processing Letters|العدد=4|سنة=1990|المجلد=35|صفحات=183–189|مؤلف1-الأول=Kurt|مؤلف2-الأول=Stefan|مؤلف2-الأخير=Naher|مؤلف1-الأخير=Mehlhorn|doi=10.1016/0020-0190(90)90022-P}}</ref>
|-
| وقت لوغاريتمي 
| [[DLOGTIME]] 
| ''يا'' (سجل ''ن'')&nbsp;''''
|log ''n'' ، log (''n ''<sup>2</sup>)&nbsp;'''''
| [[خوارزمية البحث الثنائي|بحث ثنائي]]
|-
| الوقت polylogarithmic 
|بولي (سجل ''ن'')&nbsp;''''
|(السجل ''ن'') <sup>2</sup>&nbsp;'''' 
|-
|قوة كسرية 
| ''يا'' (''ن ''<sup>ج</sup>)<div class="cx-overlay"><div class="cx-spinner"><div class="bounce1"></div><div class="bounce2"></div><div class="bounce3"></div></div></div>حيث {{تعبير رياضي|0 < c < 1}} 
| ''ن ''<sup>1/2</sup> ، ''ن ''<sup>2/3</sup> 
|البحث في شجرة دينار
|-
| الوقت الخطي 
| ''يا'' (''ن'')
| ''ن'' 
|العثور على أصغر أو أكبر عنصر في [[مصفوفة (حوسبة)|مصفوفة]] لم يتم فرزها[[مصفوفة (حوسبة)|مصفوفة]]
|-
| "n log star n" time 
| ''يا'' (''ن ''السجل *&nbsp;&nbsp;''ن'')
| خوارزمية [[تثليث مضلع|التثليث المضلع]] ل Seidel .
|-
| الوقت quasilinear 
| ''O'' (''n''&nbsp; log ''n'')&nbsp;''''
| ''ن''&nbsp; تسجيل ''ن'' ، سجل ''ن'' !&nbsp;'''''
|أسرع وقت ممكن مقارنة الفرز. [[تحويل فورييه السريع]].
|-
| الوقت التربيعي 
| ''يا'' (''ن ''<sup>2</sup>)
| ''n''<sup>2</sup> 
| [[فرز فقاعي|نوع فقاعة]]. [[ترتيب بالإدراج|نوع الإدراج]]. الالتواء المباشر
|-
| الوقت مكعب 
| ''يا'' (''ن ''<sup>3</sup>)
| ''n''<sup>3</sup> 
|الضرب السذاجة اثنين ''ن'' × ''ن'' المصفوفات. حساب الارتباط الجزئي.
|-
| وقت البولينمال 
| [[كثير حدود (تعقيد)|P]] 
|2 <sup>''O'' (log ''n'')&nbsp;''''</sup> = poly (''n'')
| ''n'' ، ''n''&nbsp; log ''n'' ، ''n ''<sup>10</sup>&nbsp;''''' 
| خوارزمية Karmarkar في ل [[برمجة خطية|البرمجة الخطية]]. [[اختبار أ.ك.أس لأولية عدد ما|اختبار البدائية AKS]]
|-
| زمن شبه كثير الحدود 
| QP 
|2 <sup>بولي (log ''n'')&nbsp;''''</sup> 
| ''n ''<sup>log &nbsp;log ''n''&nbsp;''''</sup> ، ''n ''<sup>log ''n''&nbsp;''''</sup> 
|أفضل O (سجل <sup>2 </sup> ''n'') - خوارزمية تقريب لمشكلة شجرة ستاينر الموجهة.
|-
|الوقت الأسى الفرعي <br />
(التعريف الأول)
| SUBEXP 
| ''O'' (2 <sup>''n ''<sup>''ε''</sup></sup>) لجميع ''ε''&nbsp; > &nbsp;0
| ''O ''<sup>''ن''</sup> (2 <sup>عجلة <sup>الاطارات عجلة </sup><sup>''ن''</sup>''''<sup>''''</sup></sup>)
|على افتراض افتراضات التعقيد النظرية، ويرد [[BPP]] في SUBEXP.
|-
|الوقت الأسى الفرعي <br />
(التعريف الثاني)
|2 <sup>''س'' (''ن'')</sup> 
| 2<sup>''n''<sup>1/3</sup></sup> 
|الخوارزمية الأكثر شهرة ل [[تحليل عدد صحيح إلى عوامل|توكيل تجاري صحيح]] والتماثل الرسم البياني
|-
|الوقت الأسي <br />
(مع الأس الخطي)
| E 
|2 <sup>''س'' (''ن'')</sup> 
|1.1 <sup>''ن''</sup> ، 10 <sup>''ن''</sup> 
|حل [[مسألة البائع المتجول|مشكلة مندوب المبيعات]] باستخدام [[برمجة ديناميكية|البرمجة الديناميكية]]
|-
| الوقت الأسي 
| [[EXPTIME]] 
|2 <sup>بولي (''ن'')</sup> 
| 2<sup>''n''</sup>, 2<sup>''n''<sup>2</sup></sup> 
|حل [[ضرب سلسلة مصفوفات|مضاعفة سلسلة مصفوفة]] عن طريق [[بحث شامل|البحث الغاشمة]]
|-
| الوقت مضروبة 
| ''يا'' (''ن'' !)
| ''ن'' !
|حل [[مسألة البائع المتجول|مشكلة مندوب المبيعات]] عبر [[بحث شامل|البحث]] عن [[بحث شامل|القوة الغاشمة]]
|-
| ضعف الوقت الأسي 
| 2-EXPTIME 
|2 <sup>2 <sup>بولي (''ن'')</sup></sup> 
| 2<sup>2<sup>''n''</sup></sup> 
|تقرير حقيقة بيان معين في حساب بيرسبيرغر
|}

== وقت ثابت ==
ويقال أن الخوارزمية هي '''وقت ثابت''' (مكتوب أيضًا باسم '''O (1)''') إذا كانت قيمة ''T'' (''n'') محددة بقيمة لا تعتمد على حجم المدخلات. على سبيل المثال، يستغرق الوصول إلى أي عنصر مفرد في [[مصفوفة (حوسبة)|صفيف]] وقتًا ثابتًا حيث يجب إجراء [[مجموعة التعليمات|عملية]] واحدة فقط لتحديد موقعه. بطريقة مشابهة، يتم العثور على القيمة الأدنى في مصفوفة مرتبة بترتيب تصاعدي؛ هذا هو العنصر الأول. ومع ذلك، فإن العثور على الحد الأدنى من القيمة في صفيف غير مرتبة ليس عملية زمنية ثابتة حيث يلزم إجراء مسح ضوئي فوق كل [[عنصر (رياضيات)|عنصر]] في الصفيف من أجل تحديد القيمة الأدنى.ومن ثم فهي عملية زمنية خطية تأخذ زمن O (n). إذا كان عدد العناصر معروفًا مسبقًا ولا يتغير، فإن مثل هذه الخوارزمية يمكن أن يقال إنها تعمل في وقت ثابت.

على الرغم من الاسم «وقت ثابت»، لا يجب أن يكون وقت التشغيل مستقلة عن حجم المشكلة ولكن يجب تقييد حد الأعلى وقت التشغيل بشكل مستقل عن حجم المشكلة. على سبيل المثال، فإن مهمة «تبادل قيم ''و'' و ''ب'' إذا لزم الأمر بحيث ''ل ''≤ ''ب''» ويسمى وقت ثابت على الرغم من أن الوقت قد يعتمد على ما إذا كان صحيحا أن بالفعل ''على'' ≤ ''ب'' . ومع ذلك، هناك بعض ''t'' مثل ثابت أن الوقت المطلوب هو دائما ''على الأكثر '' ''t'' .
 int index = 5؛
 int item = list [index]؛
 '''إذا''' (شرط صحيح) '''ثم'''
 تنفيذ بعض العمليات التي تعمل في وقت ثابت
 '''آخر'''
 تنفيذ بعض العمليات الأخرى التي تعمل في وقت ثابت
 '''ل''' i = 1 '''إلى''' 100
 '''لـ''' j = 1 '''to''' 200
 تنفيذ بعض العمليات التي تعمل في وقت ثابت
إذا كانت ''T'' (''n'') هي O (''أي قيمة ثابتة'')، فهذا يعادل ويقال في الترميز القياسي على أنه ''T'' (''n'') يجري O (1).

== وقت لوغاريتمي ==
ويقال إن الخوارزمية تأخذ '''وقت لوغاريتمي''' إذا كانت ''T'' (''n'') = '''O (log ''n'')''' . نظرًا لاستخدام [[نظام عد ثنائي|نظام الأرقام الثنائي]] بواسطة أجهزة الكمبيوتر، فإن [[لوغاريتم|اللوغاريتم]] يكون في الغالب أساسًا 2 (أي log <sub>2 </sub> ''n'' ، وأحيانًا مكتوبة lg ''n''). ومع ذلك، من خلال [[مطابقة لوغاريتمية|تغيير قاعدة]] لوغاريتمات، تسجيل <sub>و </sub> ''ن'' وتسجيل <sub>ب </sub> ''ن'' تختلف فقط من قبل مضاعف المستمر، والتي كبير-O يتم تجاهل التدوين. وهكذا يا (سجل ''ن'') هو الترميز القياسي لخوارزميات الوقت اللوغاريتية بغض النظر عن أساس اللوغاريتم.

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

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

يتم إعطاء مثال على الوقت اللوغاريتمي عن طريق البحث في القاموس. دعنا نفكر في [[قاموس]] يحتوي على مداخل ''n'' ، مرتبة حسب الترتيب الأبجدي. نحن نفترض أنه، بالنسبة لـ 1 ≤ ''k'' ≤ ''n''<div class="cx-overlay"><div class="cx-spinner"><div class="bounce1"></div><div class="bounce2"></div><div class="bounce3"></div></div></div>{{تعبير رياضي|1 ≤ ''k'' ≤ ''n''}}، يمكن للمرء الوصول إلى دخول ال k من القاموس في وقت ثابت. دعونا {{تعبير رياضي|''D''[''k'']}} دلالة هذا ك دخول عشر. بموجب هذه الفرضيات، يمكن إجراء الاختبار إذا كانت الكلمة D في القاموس في زمن لوغاريتمي: فكر في المكان الذي يشير إلى [[دالتا الجزء الصحيح والمتمم الصحيح الأعلى|دالة الكلمة]]. إذا تم الانتهاء من ذلك. عدا ذلك، إذا استمر البحث بنفس الطريقة في النصف الأيسر من القاموس، وإلا استمر بالمثل مع النصف الأيمن من القاموس. تشبه هذه الخوارزمية الطريقة المستخدمة غالبًا للعثور على إدخال في قاموس ورقي.<math>D(\lfloor n/2 \rfloor),</math><math>\lfloor\;\rfloor</math>[[دالتا الجزء الصحيح والمتمم الصحيح الأعلى|دالتا الجزء الصحيح و السقف]]<math>D=D(\lfloor n/2 \rfloor),</math><math>D<D(\lfloor n/2 \rfloor),</math>

== الوقت polylogarithmic ==
ويقال إن الخوارزمية تعمل في '''زمن '''polylogarithmic''' إذا كانت ''T'' (''n'') = O ((log ''n'') <sup>''k''</sup>)، لبعض ''k'' الثابت. على سبيل المثال، يمكن حل [[ضرب سلسلة مصفوفات|ترتيب سلسلة المصفوفات]] في وقت polylogarithmic على جهاز الوصول العشوائي الموازي.<ref>{{استشهاد بدورية محكمة|عنوان=Efficient Matrix Chain Ordering in Polylog Time|صحيفة=SIAM Journal on Computing|ناشر=[[Society for Industrial and Applied Mathematics]]|العدد=2|سنة=1998|المجلد=27|صفحات=466–490|issn=1095-7111|مؤلف1-الأول=Phillip G.|مؤلف2-الأول=Gregory J. E.|مؤلف2-الأخير=Rawlins|مؤلف3-الأول=Gregory E.|مؤلف3-الأخير=Shannon|مؤلف1-الأخير=Bradford|مكان=Philadelphia|doi=10.1137/S0097539794270698}}</ref>

== الوقت الفرعي الخطي ==
يقال أن الخوارزمية تعمل في '''الزمن الفرعي الخطي''' (في كثير من الأحيان '''وقت الخيط الفرعي''') إذا كانت ''T'' (''n'') = o (''n''). ويشمل ذلك على وجه الخصوص الخوارزميات مع التعقيدات الزمنية المحددة أعلاه، بالإضافة إلى خوارزميات أخرى مثل خوارزمية بحث Grover O (''n ''<sup>½</sup>).

تستخدم الخوارزميات النموذجية الدقيقة والتي يتم تشغيلها في وقت فرعي خطي [[خوارزمية متوازية|المعالجة المتوازية]] (كما يفعل حساب محدد مصفوفة NC <sub>1</sub>)، [[خوارزمية الكم|والمعالجة غير الكلاسيكية]] (كما يفعل بحث Grover)، أو بدلاً من ذلك لديها افتراضات مضمونة على هيكل الإدخال (مثل لوغاريتمي الوقت [[خوارزمية البحث الثنائي|البحث الثنائي]] والعديد من خوارزميات صيانة شجرة تفعل). ومع ذلك، قد تعتمد [[لغة شكلية|اللغات الرسمية]] مثل مجموعة جميع السلاسل التي تحتوي على 1 بت في الموضع المشار إليه من البتات log (n) الأولى من السلسلة على كل جزء من المدخلات وبعد أن تكون قابلة للحساب في الزمن الفرعي الخطي.

عادةً ما يتم حجز ''خوارزمية الوقت تحت الخطي'' محددة الخوارزميات التي تختلف عن ما سبق في أنها تعمل على نماذج الآلات التسلسلية الكلاسيكية ولا يُسمح بها افتراضات مسبقة على المدخلات.<ref>{{استشهاد بدورية محكمة|مسار=http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf|عنوان=Sublinear time algorithms|صحيفة=SIGACT News|العدد=4|سنة=2003|المجلد=34|صفحات=57–67|مؤلف1-الأول=Ravi|مؤلف2-الأول=Ronitt|مؤلف2-الأخير=Rubinfeld|مؤلف1-الأخير=Kumar|doi=10.1145/954092.954103| مسار أرشيف = https://web.archive.org/web/20160303181704/http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf | تاريخ أرشيف = 3 مارس 2016 }}</ref> ومع ذلك يسمح لهم أن تكون عشوائية، بل يجب أن تكون عشوائية للجميع ولكن أكثر المهام تافها.

على هذا النحو، يجب أن توفر الخوارزمية إجابة دون قراءة المدخلات بأكملها، وتعتمد بياناتها بشكل كبير على الوصول المسموح به إلى المدخلات. عادة للمدخلات التي يتم تمثيلها كسلسلة ثنائية ''b ''<sub>1</sub> ... ''b <sub>k</sub>'' يفترض أن الخوارزمية يمكن في الوقت المناسب طلب O (1) والحصول على قيمة ''b <sub>i</sub>'' لأي ''i'' .

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

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

الوقت الخطي هو أفضل تعقيد زمني ممكن في الحالات التي تكون فيها الخوارزمية بحاجة إلى قراءة مدخلاتها بالكامل بشكل تسلسلي. لذلك، تم استثمار الكثير من الأبحاث في اكتشاف الخوارزميات التي تعرض زمنًا خطيًا، أو على الأقل، زمنًا تقريبيًا تقريبًا. يتضمن هذا البحث كلاً من أساليب البرمجيات والأجهزة. هناك العديد من تقنيات الأجهزة التي تستغل [[حوسبة متوازية|التوازي]] لتقديم هذا. على سبيل المثال هو [[ذاكرة ذات محتوى قابل للقصد|الذاكرة المحتوى - عنونة]]. ويستخدم هذا مفهوم الزمن الخطي في خوارزميات مطابقة السلسلة مثل بوير مور خوارزمية وخوارزمية Ukkonen ل.

== الوقت شبه الخطي ==
ويقال إن الخوارزمية تعمل في زمن القصبة (يشار إليه أيضاً بوقت الخط الزمني) إذا كانت ''T'' (''n'') = '''O (''n'' log <sup>''k''</sup> '' n'')''' لبعض ''k'' الثابت الموجب؛ الوقت linearithmic هو الحال ''ك''&nbsp; = &nbsp;1.<ref>{{استشهاد بدورية محكمة|مسار=http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf|عنوان=On Quasilinear Time Complexity Theory|تاريخ=1995|صحيفة=Theoretical Computer Science|المجلد=148|صفحات=325–349|مؤلف1-الأول=Ashish V.|مؤلف2-الأول=Kenneth W.|مؤلف2-الأخير=Regan|مؤلف3-الأول=D.|مؤلف3-الأخير=Sivakumar|تاريخ الوصول=23 February 2015|مؤلف1-الأخير=Naik|doi=10.1016/0304-3975(95)00031-q| مسار أرشيف = https://web.archive.org/web/20170810163419/https://www.cse.buffalo.edu//~regan/papers/pdf/NRS95.pdf | تاريخ أرشيف = 10 أغسطس 2017 }}</ref><ref>Sedgewick، R. and Wayne K (2011). [http://algs4.cs.princeton.edu/home/ الخوارزميات ، الطبعة الرابعة] . ص. 186. بيرسون التعليم ، وشركة {{Webarchive|url=https://web.archive.org/web/20180124214150/https://algs4.cs.princeton.edu/home/ |date=24 يناير 2018}}</ref> عن طريق [[تمثيل O الكبرى|لينة O تدوين]] هذه الخوارزميات هي O (''ن''). خوارزميات الوقت الكاسيلية هي أيضاً O (''n ''<sup>1 + ε</sup>) لكل ثابت ε> 0، وبالتالي يتم تشغيلها أسرع من أي خوارزمية زمن متعدد الحدود تتضمن حدودها الزمنية مصطلح ''n ''<sup>''c''</sup> لأي ''c''&nbsp; > &nbsp;1.
* [[تصنيف دمجي|فرز الموضعي الموضعي]]، O (''n'' log <sup>''2''</sup> '' n'')
* [[ترتيب سريع|Quicksort]] ، O (''n'' log ''n'')، في نسخته العشوائية، لديه وقت تشغيل هو O (''n'' log ''n'') في توقع على مدخلات الحالة الأسوأ. تحتوي النسخة غير العشوائية على وقت تشغيل O (''n'' log ''n'') فقط عند النظر في متوسط تعقيد الحالات.
* Heapsort ، O (''n'' log ''n'')، [[تصنيف دمجي|merge sort]] ، introsort ، binary tree sort، smoothsort ، sortience sorting ، etc. in worst worst
* [[تحويل فورييه السريع|تحويلات فورييه السريعة]]، O (''n'' log ''n'')
* حساب مجموعة monge ، O (''n'' log ''n'')
في كثير من الحالات، ''ن'' · تسجيل ''ن'' إدارة الوقت هو ببساطة نتيجة أداء وΘ (سجل ''ن'') عملية ''ن'' مرات (للتدوين، انظر {{وصلة قسم|تمثيل O الكبرى|Family of Bachmann–Landau notations}}). على سبيل المثال، يؤدي فرز الشجرة الثنائية إلى إنشاء [[شجرة ثنائية]] عن طريق إدخال كل عنصر في الصفيف n-sized واحدًا تلو الآخر. نظرًا لأن عملية الإدراج على شجرة بحث ثنائية التوازن الذاتي تأخذ وقت ''O'' (log ''n'')، فإن الخوارزمية بأكملها تأخذ ''O'' (''n'' log ''n'') time.

تتطلب أنواع المقارنة عدد المقارنات ''O'' (''n'' log ''n'') على الأقل في أسوأ الحالات لأن log (''n'' !) = Θ (''n'' log ''n'')، بواسطة [[تقريب ستيرلينغ|تقريب ستيرلنغ Stirling]] . كما أنها تنشأ في كثير من الأحيان من [[علاقة استدعاء ذاتي|علاقة التكرار]] ''T'' (''n'') = 2 ''T'' (''n'' / 2) + ''O'' (''n'').

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

== وقت البولينمال ==
ويقال إن الخوارزمية تكون ذات '''زمن متعدد الحدود''' إذا كان '''وقت''' تشغيلها هو [[حدود عليا ودنيا|الحد الأعلى]] بواسطة [[متعددة الحدود|تعبير كثير الحدود]] في حجم دخل الخوارزمية، أي ''T'' (''n'') = O (''n ''<sup>''k''</sup>) لبعض ''k'' الثابت.<ref name="Sipser">{{استشهاد بكتاب|الأخير=Sipser|الأول=Michael|وصلة مؤلف=Michael Sipser|عنوان=Introduction to the Theory of Computation|سنة=2006|ناشر=Course Technology Inc|مكان=|isbn=0-619-21764-2|صفحات=}}</ref><ref>{{استشهاد بكتاب|الأخير=Papadimitriou|الأول=Christos H.|وصلة مؤلف=Christos H. Papadimitriou|عنوان=Computational complexity|مسار=https://archive.org/details/computationalcom0000papa|سنة=1994|ناشر=Addison-Wesley|مكان=Reading, Mass.|isbn=0-201-53082-1|صفحات=}}</ref> تنتمي المشاكل التي توجد لها خوارزمية زمنية حتمية متعددة الحدود إلى [[قسم تعقيد|فئة التعقيد]] '''[[كثير حدود (تعقيد)|P]]''' ، التي تعتبر مركزية في مجال [[نظرية التعقيد الحسابي]]. تنص أطروحة كوبهام أن زمن كثير الحدود هو مرادف لـ "tractable" أو «مجدي» أو «فعال» أو «سريع».<ref>{{استشهاد بكتاب|الأخير=Cobham|الأول=Alan|وصلة مؤلف=Alan Cobham|سنة=1965|الفصل=The intrinsic computational difficulty of functions|عنوان=Proc. Logic, Methodology, and Philosophy of Science II|ناشر=North Holland}}</ref>

بعض الأمثلة على خوارزميات متعددة الحدود الزمنية:
* و[[ترتيب انتقائي|اختيار نوع]] خوارزمية الفرز على ''ن'' صحيحة ينفذ عمليات لبعض المستمر ''و'' . وبالتالي فإنه يعمل في الوقت المناسب وهو خوارزمية متعددة الحدود الزمنية.<math>An^2</math>''''<math>O(n^2)</math>
* يمكن تنفيذ جميع العمليات الحسابية الأساسية (الجمع والطرح والضرب والقسمة والمقارنة) في زمن كثير الحدود.
* يمكن العثور على الحد الأقصى من التطابقات في [[رسم بياني|الرسوم البيانية]] في وقت كثير الحدود.

=== بقوة وضيق كثير الحدود ===
في بعض السياقات، وخاصة في [[استمثال (رياضيات)|التحسين]]، واحد يفرق بين '''وقت متعدد الحدود بقوة''' و '''الوقت متعدد الحدود ضعيفة''' الخوارزميات. هذان المفهومان لهما صلة فقط إذا كانت المدخلات إلى الخوارزميات تتألف من الأعداد الصحيحة.

يتم تحديد وقت كثير الحدود كثيرًا في النموذج الحسابي للحساب. في هذا النموذج من الحساب، تأخذ العمليات الحسابية الأساسية (الجمع والطرح والضرب والقسمة والمقارنة) خطوة زمنية للوحدة، بغض النظر عن أحجام المعاملات. الخوارزمية تعمل في زمن كثير الحدود جدا<ref>{{استشهاد بكتاب|الأخير=Grötschel|الأول=Martin|مؤلف1-وصلة=Martin Grötschel|مؤلف2=[[لازلو لوفاز]]|مؤلف3=[[Alexander Schrijver]]|سنة=1988|الفصل=Complexity, Oracles, and Numerical Computation|عنوان=Geometric Algorithms and Combinatorial Optimization|ناشر=Springer|isbn=0-387-13624-X}}</ref>
# يحدّد عدد العمليات في النموذج الحسابي للحساب بمتعدد الحدود في عدد الأعداد الصحيحة في مثيل المدخلات؛ و
# المساحة التي تستخدمها الخوارزمية يحدها كثيرات الحدود في حجم المدخلات.
يمكن تحويل أي خوارزمية لهذين الخواص إلى خوارزمية زمن متعددة الحدود عن طريق استبدال العمليات الحسابية بخوارزميات مناسبة لأداء العمليات الحسابية على جهاز [[آلة تورنغ|Turing]] . إذا لم يتم الوفاء بالمتطلبات الثانية المذكورة أعلاه، فهذا غير صحيح بعد الآن. وبالنظر إلى العدد الصحيح (الذي يأخذ مساحة تتناسب مع n في نموذج آلة تورينج)، فمن الممكن حساب
مع مضاعفات n باستخدام تربيع متكرر. <math>2^n</math><math>2^{2^n}</math>ومع ذلك، فإن المساحة المستخدمة لتمثيل تتناسب مع، وبالتالي الأسية بدلا من كثيرات الحدود في المساحة المستخدمة لتمثيل المدخلات.<math>2^{2^n}</math><math>2^n</math>وبالتالي، ليس من الممكن تنفيذ هذا الحساب في زمن كثير الحدود على جهاز Turing ، ولكن من الممكن حسابه من خلال العديد من العمليات الحسابية.

على العكس من ذلك، هناك خوارزميات تعمل في عدد من خطوات آلة تورينج التي تحدها حدود متعددة في طول المدخلات المشفرة الثنائية، ولكنها لا تأخذ عددًا من العمليات الحسابية يحدها كثيرات الحدود في عدد أرقام الإدخال. ومن بين الأمثلة على ذلك [[خوارزمية أقليدس|خوارزمية الإقليدية]] في حساب [[قاسم مشترك أكبر|القاسم المشترك الأكبر لعندين]] صحيحين. وبالنظر إلى اثنين الأعداد الصحيحة ويحدها وقت تشغيل الخوارزمية من قبل عدد من الخطوات آلة تورينج هذا هو متعدد الحدود في حجم تمثيل ثنائي و.<math>a</math><math>b</math><math>a</math><math>b</math>وفي نفس الوقت، لا يمكن تقييد عدد العمليات الحسابية بعدد الأعداد الصحيحة في المدخلات (وهو ثابت في هذه الحالة، فهناك دائمًا عدد صحيح فقط من المدخلات). نظرًا إلى الملاحظة الأخيرة، لا تعمل الخوارزمية في وقت كثير الحدود. وقتها تشغيل الحقيقي يعتمد على مقادير من ووليس فقط على عدد من الأعداد الصحيحة في المدخلات.<math>a</math><math>b</math>

ويقال إن الخوارزمية التي تعمل في زمن كثير الحدود لكنها ليست متعددة الحدود بقوة تعمل في '''زمن كثير الحدود''' .<ref>{{استشهاد بكتاب|الأخير=Schrijver|الأول=Alexander|وصلة مؤلف=Alexander Schrijver|سنة=2003|الفصل=Preliminaries on algorithms and Complexity|عنوان=Combinatorial Optimization: Polyhedra and Efficiency|المجلد=1|ناشر=Springer|isbn=3-540-44389-4}}</ref>
ومن الأمثلة المعروفة على المشكلة التي تعرف بها خوارزمية زمن ضيق كثير الحدود، ولكن من غير المعروف أنها تقبل خوارزمية زمن متعدد الحدود بشدة، هي [[برمجة خطية|البرمجة الخطية]]. لا ينبغي الخلط بين زمن الضيق في كثير الحدود والوقت الزائف متعدد الحدود.

=== دروس التعقيد ===
يؤدي مفهوم زمن كثير الحدود إلى عدة فصول معقدة في نظرية التعقيد الحسابي. بعض الفصول الهامة التي تم تحديدها باستخدام زمن كثير الحدود هي التالية.
* '''[[كثير حدود (تعقيد)|P]]''' : إن[[قسم تعقيد]] من المشاكل القرار لا يمكن حلها على[[آلة تورنغ|آلة تورنج حتمية]] في الوقت متعدد الحدود.
* '''[[كثير حدود غير قطعي|NP]]''' : فئة تعقيد مشاكل القرار التي يمكن حلها على آلة تورينج غير حتمية في زمن كثير الحدود.
* '''[[ZPP (تعقيد حسابي)|ZPP]]''' : فئة تعقيد مشكلات القرار التي يمكن حلها بدون أي خطأ على جهاز Turing احتمالي في زمن كثير الحدود.
* '''[[أر بي (تعقيد حسابي)|RP]]''' : فئة تعقيد مشاكل القرار التي يمكن حلها مع خطأ من جانب واحد على جهاز Turing احتمالي في زمن كثير الحدود.
* '''[[BPP]]''' : فئة تعقيد مشاكل القرار التي يمكن حلها مع وجود خطأ من جانبين على جهاز Turing احتمالي في زمن كثير الحدود.
* '''BQP''' : فئة تعقيد مشاكل القرار التي يمكن حلها مع وجود خطأ على الوجهين على[[آلة تورنغ الكمومية|آلة تورينج الكمومية]] في زمن كثير الحدود.
P هو أصغر فئة تعقيد زمني على ماكينة حتمية [[متانة (علوم الحاسب)|قوية]] من حيث تغييرات طراز الماكينة. (على سبيل المثال، تغيير من آلة تورينج شريط واحد إلى جهاز متعدد الشريط يمكن أن يؤدي إلى تسريع الدرجة الثانية، ولكن أي خوارزمية التي يتم تشغيلها في الوقت متعدد الحدود في إطار نموذج واحد كما يفعل ذلك من جهة أخرى.) أي إعطاء [[آلة مجردة]] سوف لدينا فئة تعقيد المقابلة للمشاكل التي يمكن حلها في زمن متعدد الحدود على هذا الجهاز.

== وقت حافل جدا ==
يقال أن الخوارزمية تأخذ وقتاً '''حافلاً جداً''' إذا لم تكن ''T'' (''n'') مقيدة أعلاه بواسطة أي متعدد الحدود. وباستخدام [[تمثيل O الكبرى|تدوين أوميجا قليل]]، يكون الوقت ω (''n ''<sup>''c''</sup>) لجميع الثوابت ''c'' ، حيث ''n'' هي معلمة الدخل، وهي عادة عدد البتات في المدخلات.

على سبيل المثال، تتطلب الخوارزمية التي يتم تشغيلها لخطوتين <sup>''n''</sup> عند إدخال حجم ''n'' وقتًا للسوبرى الحزبية (بشكل أكثر تحديدًا، زمنًا أسيًا).

الخوارزمية التي تستخدم موارد أسيّة هي حُرّية فائقة بشكل واضح، لكن بعض الخوارزميات ليست سوى مجرد خوارزميات سطحية جدًّا. على سبيل المثال، يتم تشغيل اختبار Adleman – Pomerance – Rumely البدائي لـ ''n ''<sup>o (log log ''n'')</sup> على مدخلات ''n'' -bit ؛ هذا ينمو أسرع من أي متعدد الحدود لأكبر ما يكفي من ''n'' ، ولكن يجب أن يصبح حجم المدخلات كبيرًا بشكل غير عملي قبل أن لا يمكن السيطرة عليه بواسطة كثير الحدود بدرجة صغيرة.

خوارزمية الذي يتطلب وقتا superpolynomial تكمن خارج [[قسم تعقيد]] '''[[كثير حدود (تعقيد)|P]]''' . تفترض أطروحة كوبهام أن هذه الخوارزميات غير عملية، وفي العديد من الحالات. نظرًا لأن [[مسألة كثير حدود وكثير حدود غير قطعي|مشكلة P vers مقابل NP]] لم يتم حلها، فإنه لا توجد حاليًا أية خوارزمية لمشكلة [[مسألة كثيرة حدود غير قطعية كاملة|NP-full والتي]] يتم تشغيلها في زمن كثير الحدود.

== زمن شبه كثير الحدود ==
'''خوارزميات '''الوقت شبه متعددة الحدود''' هي خوارزميات يتم تشغيلها بشكل أبطأ من '''زمن''' كثير الحدود، ولكنها ليست بطيئة جدًا حتى تصبح وقتًا أسيًا. أسوأ حالة تشغيل وقت خوارزمية شبه متعددة الحدود هي لبعض ثابتة. <math>2^{O((\log n)^c)}</math><math>c > 0</math>إذا كان الثابت "c" في تعريف الخوارزميات الزمنية متعددة الحدود يساوي 1، نحصل على خوارزمية زمن متعددة الحدود، وإذا كان أقل من 1، نحصل على خوارزمية وقت خطي sub-timeear.

تنشأ خوارزميات الوقت شبه متعددة الحدود عادةً في التخفيضات من مشكلة [[مسائل NP صعبة|NP-hard]] لمشكلة أخرى. على سبيل المثال، يمكن للمرء أن يأخذ مثالاً على مشكلة صلبة في NP ، على سبيل المثال 3SAT ، وتحويلها إلى مثيل لمشكلة أخرى B ، لكن حجم المثيل يصبح. <math>2^{O((\log n)^c)}</math>في هذه الحالة، لا يثبت هذا الخفض أن المشكلة B هي NP-hard ؛ هذا التخفيض يظهر فقط أنه لا توجد خوارزمية زمن متعددة الحدود لـ B ما لم يكن هناك خوارزمية زمن متعددة الحدود لـ 3SAT (وبالتالي كل [[كثير حدود غير قطعي|NP]]). وبالمثل، هناك بعض المشاكل التي نعرف خوارزميات وقت شبه متعدد الحدود، ولكن لا توجد خوارزمية زمن متعددة الحدود.هذه المشاكل تنشأ في خوارزميات التقريب. مثال مشهور هو مشكلة شجرة ستاينر الموجهة، والتي يوجد بها خوارزمية تقريب زمني متعددة الحدود تحقق عامل تقريب لـ (n عدد الرؤوس)، لكن إظهار وجود مثل هذه الخوارزمية متعددة الحدود الزمنية هو مشكلة مفتوحة.<math>O(\log^3 n)</math>

ومن المشاكل الحسابية الأخرى مع حلول الوقت متعددة الحدود، ولكن لا يوجد حل زمني متعدد الحدود، تشمل مشكلة العصب المزروع الذي يتمثل الهدف فيه في [[مشكلة المخطط الكامل ضمن مخطط|العثور على زمرة كبيرة]] في اتحاد زمرة [[رسم بياني عشوائي|ورسم بياني عشوائي]]. على الرغم من أنه شبه متعدد الحدود قابلة للحل، فقد تم افتراض أن مشكلة العصب المزروع ليس لها حل زمني متعدد الحدود. وقد استخدم هذا التخمين زمرة زرعت بمثابة [[فرض صعوبة الحساب|صلابة افتراض حسابي]] لإثبات صعوبة العديد من المشاكل الأخرى في الحسابية [[نظرية الألعاب|نظرية اللعبة]]، [[اختبار الخاصية|اختبار الملكية]]، و[[تعلم الآلة]].<ref>{{استشهاد|عنوان=ETH hardness for densest-{{mvar|k}}-subgraph with perfect completeness|سنة=2015|arxiv=1504.08352|مؤلف1-الأول=Mark|مؤلف2-الأول=Young Kun|مؤلف2-الأخير=Ko|مؤلف3-الأول=Aviad|مؤلف3-الأخير=Rubinstein|مؤلف4-الأول=Omri|مؤلف4-الأخير=Weinstein|مؤلف1-الأخير=Braverman}}</ref>

تتكون فئة '''QP''' المعقدة من جميع المشاكل التي تحتوي على خوارزميات زمنية متعددة الحدود. يمكن تعريفه من حيث DTIME على النحو التالي.<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref>
: <math>\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{(\log n)^c})</math>

=== العلاقة مع NP- مشاكل كاملة ===
في نظرية التعقيد، تسأل مشكلة [[مسألة كثير حدود وكثير حدود غير قطعي|P مقابل PN غير]] المحلولة إذا كانت جميع المشاكل في NP تحتوي على خوارزميات متعددة الحدود الزمنية. جميع خوارزميات معروفة للمشاكل [[مسألة كثيرة حدود غير قطعية كاملة|كاملة NP]] مثل 3SAT الخ تأخذ وقتا أسي. في الواقع، يتم تخمينه للعديد من المشاكل الطبيعية NP-complete التي لا تملك خوارزميات وقت أسي دون الألف. هنا، يُنظر إلى «الوقت الأسى الفرعي» ليعني التعريف الثاني المعروض أدناه. (من ناحية أخرى، فإن العديد من مشاكل الرسم البياني الممثلة بالطريقة الطبيعية من خلال المصفوفات المجاورة تكون قابلة للحل في وقت ما قبل التصنيع ببساطة لأن حجم المدخلات هو مربع عدد الرؤوس). هذا التخمين (لمشكلة k-SAT) معروف مثل فرضية الزمن الأسي.<ref name="ETH">{{استشهاد بدورية محكمة|عنوان=On the complexity of k-SAT|صحيفة=Journal of Computer and System Sciences|ناشر=[[إلزيفير]]|العدد=2|سنة=2001|المجلد=62|صفحات=367–375|issn=1090-2724|مؤلف1-الأول=R.|مؤلف2-الأول=R.|مؤلف2-الأخير=Paturi|مؤلف1-الأخير=Impagliazzo|doi=10.1006/jcss.2000.1727}}</ref> ولأنه من المتصور أن المشاكل الكاملة NP لا تحتوي على خوارزميات زمن متعددة الحدود، فإن بعض نتائج inapproximability في مجال خوارزميات التقريب تجعل الافتراض بأن مشكلات NP-complete لا تحتوي على خوارزميات زمن شبه متعددة الحدود. على سبيل المثال، راجع نتائج inapproximability المعروفة لمشكلة غطاء المجموعة.

== <div class="cx-overlay"><div class="cx-spinner"><div class="bounce1"></div><div class="bounce2"></div><div class="bounce3"></div></div></div>الوقت الأسى الفرعي ==
يستخدم مصطلح '''الزمن '''الأسى الفرعي''' للتعبير عن أن وقت تشغيل بعض الخوارزميات قد ينمو أسرع من أي حدود متعددة ولكنه لا يزال أصغر بكثير من الأس. وبهذا المعنى، فإن المشكلات التي لها خوارزميات زمنية ذات أبعاد فرعية هي أكثر قابلية للتتبع إلى حد ما عن تلك الخوارزميات الأسيّة فقط. لا يتم الاتفاق بوجه عام على التعريف الدقيق لـ «الأسى الفرعي»، <ref>{{استشهاد ويب|مسار=https://www.scottaaronson.com/blog/?p=394|عنوان=A not-quite-exponential dilemma|مؤلف=Aaronson, Scott|تاريخ=5 April 2009|عمل=Shtetl-Optimized|تاريخ الوصول=2 December 2009| مسار أرشيف = https://web.archive.org/web/20190525112826/https://www.scottaaronson.com/blog/?p=394 | تاريخ أرشيف = 25 مايو 2019 }}</ref> ونحن نذكر التعريفين الأكثر استخدامًا أدناه.

=== التعريف الأول ===
ويقال إن المشكلة تكون قابلة للحل الأسى الفرعي إذا كان من الممكن حلها في أوقات تشغيل تكون لوغاريتماتها أصغر من أي حدود متعددة. على نحو أدق، والمشكلة هي في الوقت المناسب دون الأسي إذا كان لكل لε &nbsp;> &nbsp;0 يوجد خوارزمية الذي يحل المشكلة في O الوقت (2 <sup>ن <sup>ε</sup></sup>). مجموعة جميع هذه المشاكل هي فئة التعقيد '''SUBEXP''' والتي يمكن تعريفها من حيث DTIME على النحو التالي.<ref name="bpp">{{استشهاد بدورية محكمة|عنوان=BPP has subexponential time simulations unless EXPTIME has publishable proofs|صحيفة=Computational Complexity|ناشر=[[شبرينغر|سبرنجر]]|العدد=4|سنة=1993|المجلد=3|صفحات=307–318|مؤلف1-الأول=László|مؤلف1-وصلة=László Babai|مؤلف2-الأول=Lance|مؤلف2-الأخير=Fortnow|مؤلف2-وصلة=Lance Fortnow|مؤلف3-الأول=N.|مؤلف3-الأخير=Nisan|مؤلف3-وصلة=Noam Nisan|مؤلف4-الأول=Avi|مؤلف4-الأخير=Wigderson|مؤلف4-وصلة=Avi Wigderson|مؤلف1-الأخير=Babai|مكان=Berlin, New York|doi=10.1007/BF01275486}}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{استشهاد بدورية محكمة|عنوان=Baire's Categories on Small Complexity Classes|صحيفة=[[Lecture Notes in Computer Science]]|ناشر=Springer-Verlag|سنة=2003|صفحات=333–342|issn=0302-9743|مؤلف1-الأول=P.|مؤلف1-الأخير=Moser|مكان=Berlin, New York}}
</ref><ref>{{استشهاد بدورية محكمة|عنوان=DERANDOMIZING COMPLEXITY CLASSES|صحيفة=Handbook of Randomized Computing|ناشر=Kluwer Academic Pub|سنة=2001|صفحة=843|مؤلف1-الأول=P.B.|مؤلف1-الأخير=Miltersen}}</ref>
: <math>\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)</math>
لاحظ أن هذا المفهوم للأسي الأسى غير منتظم من حيث ε بمعنى أن ε ليس جزءًا من المدخلات وقد يكون لكل have خوارزمية خاصة به لهذه المشكلة.

=== التعريف الثاني ===
يعرّف بعض المؤلفين الأزمنة الأسية الفرعية كأوقات جريان في 2 <sup>س (''ن'')</sup> .<ref>{{استشهاد بدورية محكمة|عنوان=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem|صحيفة=SIAM Journal on Computing|ناشر=[[Society for Industrial and Applied Mathematics]]|العدد=1|سنة=2005|المجلد=35|صفحة=188|issn=1095-7111|مؤلف1-الأول=Greg|مؤلف1-الأخير=Kuperberg|مكان=Philadelphia|doi=10.1137/s0097539703436345}}</ref><ref>{{cite arXiv|eprint=quant-ph/0406151v1|مؤلف1=Oded Regev|عنوان=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|class=quant-ph|سنة=2004}}</ref> يسمح هذا التعريف بأوقات تشغيل أكبر من التعريف الأول للوقت الأسى الفرعي. مثال على مثل هذه الخوارزمية ذات الأسيّة الفرعية هي أفضل خوارزمية كلاسيكية معروفة لتحقيق عامل صحيح، المنخل العام لأعداد الأرقام، والذي يعمل في الوقت المناسب ، حيث يكون طول المدخلات ''n'' . <math>2^{\tilde{O}(n^{1/3})}</math>''''مثال آخر هو خوارزمية معروفة لمشكلة تشابه الرسم البياني ، والتي تعمل في الوقت المناسب .<math>2^{O(\sqrt{n \log n})}</math>

لاحظ أنه يحدث فرقًا ما إذا كان يُسمح للخوارزمية أن تكون أسيةً فرعيةً في حجم المثيل ، أو عدد الرؤوس ، أو عدد الحواف. في التعقيد المعلمات ، يتم توضيح هذا الاختلاف عن طريق النظر في أزواج من مشاكل القرار والمعلمات ''k'' . <math>(L,k)</math>''''SUBEPT''' هو فئة جميع المشاكل المعلمات التي تعمل في الوقت الأسي الفرعي في ''k'' ومتعدّد الحدود في حجم المدخلات ''n'' :<ref>{{استشهاد بكتاب|الأخير=Flum|الأول=Jörg|مؤلف2-الأخير=Grohe|مؤلف2-الأول=Martin|عنوان=Parameterized Complexity Theory|سنة=2006|ناشر=Springer|مسار= https://www.springer.com/gp/book/9783540299523|isbn=978-3-540-29952-3|تاريخ الوصول=2010-03-05|صفحة=417|مسار أرشيف= https://web.archive.org/web/20071118193434/http://www.springer.com:80/east/home/generic/search/results?SGWID=5-40109-22-141358322-0|تاريخ أرشيف=2007-11-18}}</ref>
: <math>\text{SUBEPT}=\text{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right).</math>
بتعبير أدق ، SUBEPT هو فئة من جميع المشاكل المعلمات التي لها [[دالة قابلة للحساب|دالة حسابية]] مع خوارزمية تقرر ''L'' في الوقت المناسب .<math>(L,k)</math>[[دالة قابلة للحساب|دوال حسابية]] <math>f : \mathbb N\to\mathbb N</math><math>f \in o(k)</math>''''<math>2^{f(k)} \cdot \text{poly}(n)</math>

==== فرضية الزمن الأسي ====
على '''فرضية الوقت الأسي''' ('''ETH''') هي أن 3SAT ، والمشكلة satisfiability من الصيغ المنطقية في نموذج عطف نظامي مع، على الأكثر، وثلاث الحرفية في بند ومع ''ن'' المتغيرات، لا يمكن حلها في الوقت المناسب 2 <sup>''س'' (''ن'')</sup> . بتعبير أدق ، فإن الفرضية هي أن هناك بعض الثابت المطلق ''c'' > 0<div class="cx-overlay"><div class="cx-spinner"><div class="bounce1"></div><div class="bounce2"></div><div class="bounce3"></div></div></div>بحيث لا يمكن تحديد 3SAT في الوقت المناسب 2 <sup>''CN من''</sup> قبل أي آلة تورينج حتمية. من خلال ''m'' تشير إلى عدد الفقرات ، تعادل ETH الفرضية القائلة بأنه لا يمكن حل ''k'' SAT في الوقت 2 <sup>''o'' (''m'')</sup> لأي عدد صحيح {{تعبير رياضي|''k''&nbsp;≥&nbsp;3}} .<ref>{{استشهاد بدورية محكمة|عنوان=Which problems have strongly exponential complexity?|صحيفة=[[Journal of Computer and System Sciences]]|العدد=4|سنة=2001|المجلد=63|صفحات=512–530|مؤلف1-الأول=R.|مؤلف1-وصلة=Russell Impagliazzo|مؤلف2-الأول=R.|مؤلف2-الأخير=Paturi|مؤلف3-الأول=F.|مؤلف3-الأخير=Zane|مؤلف1-الأخير=Impagliazzo|doi=10.1006/jcss.2001.1774}}</ref> تعني الفرضية الزمنية الأسية [[مسألة كثير حدود وكثير حدود غير قطعي|P ≠ NP]] .

== الوقت الأسي ==
يقال أن الخوارزمية هي '''وقت أسي''' ، إذا كانت ''T'' (''n'') أعلى من 2 <sup>poly (''n'')</sup> ، حيث يكون poly (''n'') متعدد الحدود في ''n'' . بشكل أكثر رسمية ، الخوارزمية هي وقت أسي إذا كانت ''T'' (''n'') يحدها O (2 <sup>''n ''<sup>''k''</sup></sup>) لبعض ''k'' الثابت . المشاكل التي تعترف خوارزميات الأسيّة الزمنية على آلة تورنج حتمية تشكل فئة التعقيد المعروفة بـ '''[[EXPTIME]]''' .
: <math>\text{EXP} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{n^c}\right)</math>
في بعض الأحيان ، يتم استخدام الزمن الأسي للرجوع إلى الخوارزميات التي تحتوي على ''T'' (''n'') = 2 <sup>O (''n'')</sup> ، حيث تكون الأسس على الأغلب دالة خطية لـ ''n'' . وهذا يثير الطبقة تعقيد '''E''' .
: <math>\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)</math>

== ضعف الوقت الأسي ==
يقال أن الخوارزمية تكون مزدوجة الأسيّة إذا كانت ''T'' (''n'') أعلى من 2 <sup>2 <sup>بولي (''n'')</sup></sup> ، حيث تكون poly (''n'') متعددة الحدود في ''n'' . تنتمي هذه الخوارزميات إلى فئة التعقيد 2-EXPTIME .
: <math>\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}\left( 2^{2^{n^c}}\right)</math>
تتضمن خوارزميات الوقت الأسية المعروفة جيداً:
* إجراءات اتخاذ القرار في حساب برغر بيرجر
* حساب أساس Gröbner (في أسوأ الحالات <ref>ماير، E. & Mayer، A: The Complexity of Word Problem for Commutative Semi-groups and Colynomial Ideals. ''حال. في الرياضيات. ''46 (1982) pp. 305-329</ref>)
* يأخذ القضاء على كمية على الحقول المغلقة الحقيقية على الأقل ضعف الوقت الأسي ، <ref>JH Davenport & J. Heintz: Real Quantifier Elimination is Doubly Doubly.
''J. شركات رمزية. ''5 (1988) pp. 29-35.</ref> ويمكن القيام به في هذا الوقت.<ref>جنرال الكتريك كولينز: القضاء على المكملة الحقيقية من الحقول المغلقة عن طريق تحلل الجبرية أسطواني. بروك. 2. GI Conference Automata Theory & Formal Languages (Springer Lecture Notes in Computer Science 33) pp. 134-183</ref>

== انظر أيضًا ==
* L-تصنيف
* تعقيد الفضاء

== المراجع ==
{{مراجع|colwidth=33em}}
{{شريط بوابات|تقانة|علوم|علم الحاسوب}}

[[تصنيف:تحليل الخوارزميات]]
[[تصنيف:زمن]]
[[تصنيف:نظرية التعقيد الحسابي]]