كثير من اقسام التعقيد يمكن تعريفها بواسطة تحديد الوقت او المكان التي تستخدمها الخوارزمية وفي هذا السياق يمكن تعريف بعض الاقسام كالتالي :
| اقسام تعقيد | النموذج الحاسوبي | قيود الموارد |
|---|---|---|
| ((DTIME(f(n | آلة تيورنج قطعية | وقت (f(n |
| P | آلة تيورنج قطعية | وقت (poly(n |
| EXPTIME | آلة تيورنج قطعية | وقت(2poly(n |
| ((NTIME(f(n | آلة تيورنج غير قطعية | وقت (f(n |
| NP | آلة تيورنج غير قطعية | وقت (poly(n |
| NEXPTIME | آلة تيورنج غير قطعية | وقت (2poly(n |
| ((DSPACE(f(n | آلة تيورنج قطعية | مكان (f(n |
| L | آلة تيورنج قطعية | مكان (O(log n |
| بيسبايس | آلة تيورنج قطعية | مكان (poly(n |
| EXPSPACE | آلة تيورنج قطعية | مكان (2poly(n |
| ((NSPACE(f(n | آلة تيورنج غير قطعية | مكان (f(n |
| NL | آلة تيورنج غير قطعية | مكان (O(log n |
| بيسبايس | آلة تيورنج غير قطعية | مكان (poly(n |
| NEXPSPACE | آلة تيورنج غير قطعية | مكان (2poly(n |
ليست هناك تعليقات:
إرسال تعليق