Informatika sohasida vaqt murakkabligi algoritmning kirish ma’lumotlarini ifodalovchi satr uzunligining funksiyasi sifatida aniqlanadi va u ayni kirish ma’lumotlari uchun algoritmning ishlash vaqtiga teng bo‘ladi. Algoritmning vaqt murakkabligi odatda katta O notatsiyasi bilan ifodalanadi; bunda faqat eng yuqori darajali had hisobga olinadi, doimiy ko‘paytuvchilar, ya’ni koeffitsiyentlar e’tiborga olinmaydi. Murakkablik shu tarzda ifodalansa, asimptotik vaqt murakkabligi tavsifi haqida gapiriladi, ya’ni kirish hajmi cheksizlikka intilgandagi holat nazarda tutiladi. Masalan, agar , shundayki, uzunligi bo‘lgan barcha kirish ma’lumotlari uchun algoritmning ishlash vaqti dan oshmaydi; demak, bu algoritmning vaqt murakkabligini asimptotik ravishda quyidagicha baholash mumkin: .
Algoritmning vaqt murakkabligi odatda u bajaradigan elementar amallar sonini sanash orqali baholanadi. Bunda har bir elementar amalni bajarish vaqti doimiy deb olinadi, ya’ni asimptotik jihatdan . Bunday belgilashda algoritmning umumiy bajarilish vaqti bilan bajarilgan elementar amallar soni ko‘pi bilan doimiy ko‘paytuvchiga farq qiladi; O-notatsiyada bu ko‘paytuvchi hisobga olinmaydi. Algoritmning ishlash vaqti bir xil hajmdagi kirish ma’lumotlari uchun ham farq qilishi mumkinligi sababli, odatda eng yomon holatdagi ishlash vaqti bilan belgilanadi va u kirish uzunligi bo‘lgan barcha ma’lumotlar uchun algoritmning eng katta ishlash vaqtini anglatadi. Kamroq hollarda, odatda bu alohida qayd etiladi, o‘rtacha murakkablik[inglizcha], ya’ni matematik kutilma barcha mumkin bo‘lgan kirish ma’lumotlari bo‘yicha ishlash vaqtini anglatadi. Algoritmning ishlash vaqtini O-notatsiya ostidagi funksiyaga qarab tasniflash mumkin. Masalan, qiymatli algoritm chiziqli vaqtli algoritm deb ataladi; , algoritm esa biror darajali ko‘phad bilan chegaralangan vaqtda ishlaydi; u ko‘phadli.
Vaqt murakkabligi sinflari jadvali
Quyidagi jadvalda eng ko‘p uchraydigan murakkablik sinflari. Jadvalda ixtiyoriy ko‘phadni bildiradi, ya’ni .
| Nomi | Murakkablik sinfi | Ishlash vaqti, | Ishlash vaqtiga misollar | Algoritmlarga misollar |
|---|---|---|---|---|
| doimiy vaqt | Butun sonning juft yoki toqligini aniqlash (ikkilik ko‘rinishda ifodalangan) | |||
| Akkerman funksiyasining teskari funksiyasi | Amortizatsion tahlil har bir amal uchun, o‘zaro kesishmaydigan to‘plamlar | |||
| iteratsion logarifmik vaqt | Sikllarni taqsimlangan ranglash | |||
| ikki karra logarifmik | Chegaralangan prioritet navbatidan foydalanganda bitta amal uchun amortizatsiyalangan vaqt[inglizcha] | |||
| logarifmik vaqt | DLOGTIME[inglizcha] | , | Ikkilik qidiruv | |
| polilogarifmik vaqt | ||||
| subchiziqli vaqt | uchun | , | Qidirish k-o‘lchamli daraxtda | |
| chiziqli vaqt | Eng kichik yoki eng katta elementni saralanmagan massivdan qidirish | |||
| «n log-yulduzcha n» | Algoritm ko‘pburchakni triangulyatsiyalash Zaydel[inglizcha]. | |||
| chiziqli-logarifmik vaqt | , | Eng tez taqqoslashga asoslangan saralash[inglizcha] | ||
| kvadratik vaqt | Pufakchali saralash, qo‘shish orqali saralash, to‘g‘ridan-to‘g‘ri konvolyutsiya | |||
| kubik vaqt | Ikki matritsani oddiy ko‘paytirish ikkita matritsaning ko‘paytmasi. Qisman korrelyatsiyani hisoblash[inglizcha]. | |||
| ko‘phadli vaqt | P | , , | Karmarkar algoritmi uchun chiziqli dasturlash, AKS tub sonlik testi | |
| kvaziko‘phadli vaqt | QP | , | Ma’lum bo‘lgan eng tez — yaqinlashtirish algoritmi yo‘naltirilgan Shtayner masalasi. | |
| subeksponensial vaqt (birinchi ta’rif) | SUBEXP | barcha | Nazariy farazlarni qabul qilsak, BPP SUBEXP sinfiga kiradi. | |
| subeksponensial vaqt (ikkinchi ta’rif) | Eng tez ma’lum algoritmlar butun sonlarni ko‘paytuvchilarga ajratish va graflar izomorfizmi[inglizcha] | |||
| eksponensial vaqt (chiziqli eksponent bilan) | E[inglizcha] | , | Yechish: sayohatchi sotuvchi masalasi yordamida dinamik dasturlash | |
| eksponensial vaqt | EXPTIME | , | Yechish: matritsalarni ko‘paytirish tartibi masalasi yordamida to‘liq qidiruv | |
| faktorial vaqt | Yechish: sayohatchi sotuvchi masalasi to‘liq qidiruv orqali | |||
| ikki karra eksponensial vaqt | 2-EXPTIME[inglizcha] | Berilgan mulohazaning to‘g‘riligini Presburger arifmetikasida tekshirish | ||
| Yevklid algoritmi | ||||
| Polig–Hellman algoritmi | Agar sonning ajratiladigan ko‘paytuvchilari yetarlicha kichik bo‘lsa, algoritm juda samarali ishlaydi | |||
| Pollardning ρ-usuli | Murakkablikning evristik bahosiga ega |
Doimiy vaqt
Algoritm doimiy vaqtli algoritm deb ataladi (ishlash vaqti ko‘rinishida yoziladi), agar qiymati kirish hajmiga bog‘liq bo‘lmagan qiymat bilan chegaralangan bo‘lsa. Masalan, massivdagi bitta elementni olish doimiy vaqtni oladi, chunki uni topish uchun faqat bitta buyruq bajariladi. Biroq saralanmagan massivdagi eng kichik qiymatni topish doimiy vaqtli amal emas, chunki massivning har bir elementini ko‘rib chiqishimiz kerak. Demak, bu amal chiziqli vaqtni oladi, . Agar elementlar soni oldindan ma’lum va o‘zgarmas bo‘lsa, bunday algoritmni doimiy vaqtli algoritm deb hisoblash mumkin.
«Doimiy vaqt» degan nomga qaramay, ishlash vaqti masala o‘lchamiga bog‘liq bo‘lmasligi shart emas; faqat ishlash vaqtining yuqori chegarasi o‘zgarmas bo‘lishi kerak. Masalan, «agar zarur bo‘lsa, va qiymatlarini qiymati hosil bo‘ladigan tarzda almashtirish» masalasi doimiy vaqtli hisoblanadi, garchi algoritmning ishlash vaqti tengsizlik bajarilganmi yoki yo‘qmi, shunga bog‘liq bo‘lishi mumkin. Biroq shunday doimiy son mavjudki, masalani bajarish vaqti hech qachon oshmaydi .
Quyida doimiy vaqtda ishlaydigan kodga misol keltirilgan:
int index = 5;
int item = list[index];
if (условие верно) then
выполнить некоторые операции с постоянным временем работы
else
выполнить некоторые операции с постоянным временем работы
for i = 1 to 100
for j = 1 to 200
выполнить некоторые операции с постоянным временем работы
Agar qiymati ga teng bo‘lsa, bu yerda — doimiy son, bu qiymatiga teng bo‘lishi bilan ekvivalent..
Logarifmik vaqt
Algoritm logarifmik vaqtda, agar . Kompyuterlarda ikkilik sanoq tizimi, logarifm asosi sifatida logarifm ishlatiladi (ya’ni ). Biroq logarifm asosini almashtirganda va faqat o‘zgarmas ko‘paytuvchiga farq qiladi , u katta O notatsiyasida hisobga olinmaydi. Shunday qilib, logarifmik vaqt algoritmlari uchun standart yozuv hisoblanadilogarifmik vaqt logarifm asosidan qat’i nazar.
Logarifmik vaqtda ishlaydigan algoritmlar odatda ikkilik daraxtlar bilan ishlashda yoki ikkilik qidiruv.
yordamida uchraydi. Hajmi bo‘lgan massivlar bilan ishlaydigan algoritmlar yuqori samarali hisoblanadi, chunki bitta amalni bajarish vaqtining massiv hajmiga nisbati uning hajmi ortgani sari kamayadi.
Bunday algoritmning juda sodda misoli — lug‘atdan so‘z qidirish. Unda ta so‘z alifbo tartibida saralangan deb faraz qilaylik. Bunda barcha so‘zlarning uzunligi ga teng va lug‘atning istalgan elementiga indeks orqali doimiy vaqtda murojaat qilish mumkin deb hisoblaymiz. Faraz qilaylik, — bu -lug‘at elementi bo‘lsin. Shunda so‘zining lug‘atda bor-yo‘qligini vaqt ichida tekshirish mumkin. Buning uchun lug‘atning elementini ko‘rib chiqish kerak; bu yerda quyidagini bildiradi: sonni pastga qarab yaxlitlash. Agar bo‘lsa, massivning o‘ng yarmiga, aks holda chap yarmiga o‘tish kerak. Oxirida berilgan so‘zga teng yoki undan leksikografik jihatdan katta bo‘lgan birinchi so‘zning indeksini olamiz: .
int find(vector<string> &D, string w) {
int n = D.size();
int l = -1, r = n;
while(r - l > 1) {
int m = (l + r) / 2;
if(D[m] < w) {
l = m;
} else {
r = m;
}
}
return r;
}
Polilogarifmik vaqt
Algoritm polilogarifmik vaqtda ishlaydi, agar biror . Masalan, matritsalarni ko‘paytirish tartibi masalasi bunday vaqtda yechilishi mumkin parallel RAM mashinasida[inglizcha].
Subchiziqli vaqt
Algoritm subchiziqli vaqtda ishlaydi, agar . Xususan, bunga yuqorida keltirilgan vaqt murakkabligiga ega algoritmlar, shuningdek, masalan, Grover qidiruvi (murakkabligi .
Odatda, aniq natija beradigan bo‘lsa-da, subchiziqli vaqtda ishlaydigan algoritmlar jarayonlarni parallellashtirishdan foydalanadi (masalan, NC algoritmi 1 matritsa determinantini hisoblashda shunday qiladi), noklassik hisoblashlardan (masalan, Grover qidiruvida) yoki kirish ma’lumotlari tuzilishi haqida kafolatlangan farazga tayanadi (masalan, ikkilik qidiruv algoritmlari va daraxtlarni qayta ishlashning ko‘plab algoritmlari). Biroq formal tillar, masalan, so‘zning dastlabki biti bilan aniqlanadigan pozitsiyada bitta biti mavjud bo‘lgan so‘zlar tili subchiziqli vaqtda yechilishi mumkin, garchi so‘zning istalgan biti uning shu tilga tegishli yoki tegishli emasligini aniqlashda muhim bo‘lishi mumkin.
Atama subchiziqli vaqtda ishlaydigan algoritm odatda yuqoridagi misollardan farqli ravishda, oddiy ketma-ket mashina modellarida ishlaydigan va kirish ma’lumotlari tuzilishi haqida oldindan ma’lumotga ega bo‘lishni talab qilmaydigan algoritmlarga nisbatan ishlatiladi. Biroq ularda ehtimollik usullaridan foydalanishga ruxsat beriladi; bundan tashqari, ko‘pincha ular albatta har qanday trivial bo‘lmagan masala uchun tasodifiylashtirilgan bo‘lishi kerak.
Bunday algoritm kirish ma’lumotlarini to‘liq o‘qimasdan javob berishi kerakligi sababli, u kirish oqimida ruxsat etilgan murojaat usullariga juda kuchli darajada bog‘liq. Odatda, bitlar satri ko‘rinishidagi oqim uchun algoritm vaqt ichida istalgan .
Subchiziqli vaqt algoritmlari odatda ehtimollik asosida ishlaydi va faqat taqribiy yechim beradi. Subchiziqli vaqtda ishlaydigan algoritmlar tabiiy ravishda xossalarni tekshirish[inglizcha].
Chiziqli vaqt
Aytishlaricha, algoritm chiziqli vaqtda yoki vaqtida ishlaydi, agar uning murakkabligi ga teng bo‘lsa. Norasmiy aytganda, bu yetarlicha katta kirish ma’lumotlari uchun ishlash vaqti kirish hajmiga chiziqli ravishda bog‘liq holda ortishini anglatadi. Masalan, ro‘yxatdagi barcha elementlarni yig‘adigan protsedura ro‘yxat uzunligiga mutanosib vaqt talab qiladi. Bu ta’rif mutlaqo aniq emas, chunki ishlash vaqti aniq mutanosiblikdan sezilarli farq qilishi mumkin, ayniqsa kichik .
Chiziqli vaqt ko‘pincha algoritm uchun istalgan xususiyat deb qaraladi. (Deyarli) chiziqli yoki undan ham tez ishlaydigan algoritmlarni yaratish bo‘yicha ko‘plab tadqiqotlar olib borilgan. Bu tadqiqotlar dasturiy va apparat yondashuvlarini qamrab olgan. Apparat yordamida bajarish holatida, matematik nuqtayi nazardan standart hisoblash modellarida chiziqli bajarilish vaqtiga hech qachon erisha olmaydigan ayrim algoritmlar chiziqli vaqtda ishlashi mumkin. Bunday maqsadga erishish uchun ayrim apparat texnologiyalari parallellikdan foydalanadi. Bunga assotsiativ xotira misol bo‘ladi. Chiziqli vaqt tushunchasi andozaga moslashtirish masalalarida, jumladan, Boyer–Mur algoritmi va Ukkonen algoritmida.
Kvazichiziqli vaqt
Algoritm kvazichiziqli vaqtda ishlaydi, agar biror doimiy . bo‘lganda, chiziqli-logarifmik vaqt deyiladi. soft-O notatsiyasida bunday ishlash vaqti ko‘rinishida yoziladi. Kvazichiziqli vaqt algoritmlari uchun quyidagi baho ham o‘rinli: har qanday . Demak, bu algoritmlar darajasi .
dan katta bo‘lgan istalgan ko‘phaddan tezroq ishlaydi. Yuqorida aytib o‘tilgan chiziqli-logarifmik algoritmlardan tashqari, kvazichiziqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:
- Joyida birlashtirib saralash: ;
- Tezkor saralash: algoritmning tasodifiylashtirilgan versiyasida ishlash vaqtining matematik kutilmasi har qanday kirish ma’lumotlari uchun deterministik versiyada esa bu baho faqat barcha kirishlar bo‘yicha o‘rtacha qiymat uchun to‘g‘ri;
- Piramida yordamida saralash, Birlashtirib saralash, introsort, ikkilik daraxt yordamida saralash, silliq saralash, pasyans saralash[inglizcha] va boshqalar: eng yomon holatda;
- Tezkor Furye o‘zgartirishi: ;
- Algoritmlar Monj matritsalarida: .
Chiziqli-logarifmik vaqt
Chiziqli-logarifmik vaqt kvazichiziqli vaqtning xususiy holi bo‘lib, logarifmik ko‘paytuvchining darajasi ga teng.
Chiziqli-logarifmik funksiya — bu ko‘rinishdagi funksiya (ya’ni chiziqli va logarifmik hadlarning ko‘paytmasi). Algoritm chiziqli-logarifmik vaqtda ishlaydi, agar . Shunday qilib, chiziqli-logarifmik funksiya chiziqli funksiyadan tezroq, ammo darajasi dan katta bo‘lgan .
istalgan ko‘phaddan sekinroq o‘sadi. Ko‘p hollarda ishlash vaqti shunchaki marta bajariladigan, ishlash vaqti bo‘lgan amal natijasi bo‘ladi. Masalan, ikkilik daraxt yordamida saralash algoritmi ikkilik daraxt ni hajmi bo‘lgan massivning har bir elementini navbatma-navbat unga kiritish orqali hosil qiladi. Muvozanatlangan ikkilik qidiruv daraxtiga[inglizcha] element kiritish amali vaqt olgani uchun algoritmning umumiy bajarilish vaqti chiziqli-logarifmik bo‘ladi.
Har qanday taqqoslashga asoslangan saralash[inglizcha] eng yomon holatda kamida chiziqli-logarifmik sondagi taqqoslashlarni talab qiladi. Buni axborot nazariyasi nuqtayi nazaridan sodda tarzda quyidagicha asoslash mumkin: saralash natijasida uzunligi bo‘lgan va elementlar tartibini bir qiymatli belgilaydigan o‘rin almashtirish hosil bo‘ladi. Jami xil saralash tartibi mavjud; agar ularning har birini bitlar ketma-ketligi bilan bir qiymatli kodlamoqchi bo‘lsak, har bir o‘rin almashtirishga o‘rtacha kamida bit axborot kerak bo‘ladi. Massivning ikki elementini o‘zaro taqqoslash natijasi esa aynan bir bit axborot beradi: birinchi element ikkinchisidan kichik yoki kichik emas. Demak, saralash uchun faqat juft-juft taqqoslashlardan foydalansak, massivni vaqtdan tezroq saralash eng yomon holatda mumkin emas. Boshqa tomondan, bunday baho ko‘plab rekursiv saralash algoritmlarida, masalan, birlashtirib saralash uchun ko‘pincha rekurrent tenglamadan .
Subkvadratik vaqt
Aytishlaricha, algoritm subkvadratik vaqtda ishlaydi, agar .
Masalan, oddiy saralash algoritmlari, taqqoslashga asoslangan (masalan, qo‘shish orqali saralash) kvadratik vaqtli hisoblanadi. Shu bilan birga, subkvadratik vaqtda ishlaydigan yanada takomillashgan algoritmlar ham mavjud (masalan, Shell saralashi). Umumiy turdagi saralash algoritmlarining hech biri chiziqli vaqtda ishlamaydi, biroq kvadratik vaqtdan subkvadratik vaqtga o‘tish amaliy jihatdan juda muhim.
Ko‘phadli vaqt
Algoritm ko‘phadli vaqtda, agar ishlash vaqti yuqoridan ko‘phad bilan algoritm kirish ma’lumotlari hajmiga nisbatan chegaralangan bo‘lsa, ya’ni biror doimiy . Masalalar, ular uchun deterministik ko‘phadli vaqt algoritmlari mavjud bo‘lsa, murakkablik sinfini P tashkil qiladi; u hisoblash murakkabligi nazariyasida markaziy o‘rin tutadi. Kobem tezisi[inglizcha] ko‘phadli vaqtni «oson qayta ishlanadigan», «bajarish mumkin bo‘lgan», «samarali» yoki «tez» tushunchalari bilan tenglashtiradi.
Ko‘phadli algoritmlarga misollar:
- Butun sonlarni saralovchi tezkor saralash algoritmi biror doimiy uchun ko‘pi bilan ta amal bajaradi. Demak, u vaqtda ishlaydi va ko‘phadli algoritm hisoblanadi.
- Barcha asosiy arifmetik amallar (qo‘shish, ayirish, ko‘paytirish, bo‘lish va taqqoslash) ko‘phadli vaqtda bajarilishi mumkin.
- Maksimal moslikgraflarida ko‘phadli vaqtda topilishi mumkin.
Qat’iy va kuchsiz ko‘phadli vaqt
Ayrim kontekstlarda, ayniqsa optimallashtirishda, qat’iy ko‘phadli vaqt va kuchsiz ko‘phadli vaqt algoritmlari farqlanadi. Bu ikki tushuncha faqat butun sonlardan tashkil topgan kirish ma’lumotlariga taalluqlidir.
Qat’iy ko‘phadli vaqt hisoblashning arifmetik modelida aniqlanadi. Bu modelda asosiy arifmetik amallar (qo‘shish, ayirish, ko‘paytirish, bo‘lish va taqqoslash) operandlar uzunligidan qat’i nazar, bir birlik vaqt oladi deb hisoblanadi. Algoritm quyidagi shartlarda qat’iy ko‘phadli vaqtda ishlaydi:
- hisoblashning arifmetik modelidagi amallar soni kirish oqimidagi butun sonlar soniga nisbatan ko‘phad bilan chegaralangan bo‘lishi; va
- algoritm foydalanadigan xotira hajmi kirish ma’lumotlari o‘lchamiga nisbatan ko‘phad bilan chegaralangan bo‘lishi kerak.
Bu ikki xususiyatga ega har qanday algoritmni arifmetik amallarni Tyuring mashinasida bajariladigan tegishli arifmetik amallar algoritmlari bilan almashtirish orqali ko‘phadli vaqt algoritmiga aylantirish mumkin. Agar yuqoridagi ikkinchi talab bajarilmasa, bu xulosa endi to‘g‘ri bo‘lmaydi. Agar butun soni berilgan bo‘lsa (u Tyuring mashinasida n ga mutanosib xotira egallaydi), ni takroriy darajaga oshirish yordamida n ta amal bilan hisoblash mumkin. Biroq ni ifodalash uchun sarflanadigan xotira ga mutanosib bo‘lib, kirish ma’lumotlari uchun ishlatiladigan xotiraga nisbatan ko‘phadli emas, balki eksponensial ravishda o‘sadi. Shu sababli bu hisoblashlarni Tyuring mashinasida ko‘phadli vaqtda bajarib bo‘lmaydi, ammo ko‘phadli sondagi arifmetik amallar bilan bajarish mumkin.
Aksincha, Tyuring mashinasidagi qadamlari ikkilik shaklda kodlangan kirish ma’lumotlari uzunligiga nisbatan ko‘phad bilan chegaralangan, biroq kirishdagi sonlar miqdoriga nisbatan ko‘phadli sondagi arifmetik amallar bilan bajarilmaydigan algoritmlar ham mavjud. Yevklid algoritmi orqali eng katta umumiy bo‘luvchini ikki butun son uchun hisoblash bunga misol bo‘ladi. Ikkita va butun soni uchun algoritmning ishlash vaqti ta Tyuring mashinasi qadami bilan chegaralanadi. Bu son va sonlarining ikkilik ko‘rinishdagi uzunligiga nisbatan ko‘phad bo‘lib, uni taxminan tarzida ifodalash mumkin. Shu bilan birga, arifmetik amallar sonini kirishdagi butun sonlar soni bilan chegaralab bo‘lmaydi (bu holatda u o‘zgarmas — kirishda atigi ikkita son bor). Shu sababli algoritm qat’iy ko‘phadli vaqtda ishlamaydi. Algoritmning haqiqiy ishlash vaqti kirishdagi butun sonlar sonigagina emas, balki ularning va qiymatlariga ham bog‘liq.
Agar algoritm ko‘phadli vaqtda ishlasa-yu, qat’iy ko‘phadli vaqtda ishlamasa, u kuchsiz ko‘phadli vaqtda ishlaydi deyiladi. Qat’iy ko‘phadli algoritmi ma’lum bo‘lmagan, ammo kuchsiz ko‘phadli algoritmi ma’lum bo‘lgan masalaning mashhur namunasi — chiziqli dasturlash. Kuchsiz ko‘phadli vaqtni psevdoko‘phadli vaqt.
Murakkablik sinflari
Ko‘phadli vaqt tushunchasi hisoblash murakkabligi nazariyasida bir nechta murakkablik sinflarini yuzaga keltiradi. Quyida ko‘phadli vaqt yordamida aniqlanadigan muhim sinflarning ayrimlari keltirilgan.
- P: Qaror masalalarining murakkablik sinfi bo‘lib, ularni deterministik Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
- NP: qaror masalalarining murakkablik sinfi; ularni nodeterministik Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
- ZPP: qaror masalalarining murakkablik sinfi; ularni nol xato bilan ehtimollik Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
- RP: qaror masalalarining murakkablik sinfi; ularni bir tomonlama xatolarga yo‘l qo‘ygan holda ehtimollik Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
- BPP: qaror masalalarining murakkablik sinfi; ularni ikki tomonlama xatolarga yo‘l qo‘ygan holda ehtimollik Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
- BQP: qaror masalalarining murakkablik sinfi; ularni ikki tomonlama xatolarga yo‘l qo‘ygan holda kvant Tyuring mashinasida ko‘phadli vaqtda yechish mumkin.
P deterministik mashinadagi vaqt murakkabligining mashina modelini o‘zgartirishga nisbatan barqaror[inglizcha] bo‘lgan eng kichik sinfidir. (Masalan, bir lentali Tyuring mashinasidan ko‘p lentali mashinaga o‘tish hisoblashni kvadratik tezlashtirishi mumkin, ammo bir modelda ko‘phadli vaqtda ishlaydigan har qanday algoritm boshqa modelda ham ko‘phadli vaqtda ishlaydi.)
Superko‘phadli vaqt
Algoritm superko‘phadli vaqtda ishlaydi, agar T(n) qiymati yuqoridan hech qanday ko‘phad bilan chegaralanmagan. Bunday ishlash vaqti ω(nc) ko‘rinishida bo‘ladi; barcha doimiy c uchun; bu yerda n — kirish parametri, odatda kirish ma’lumotlaridagi bitlar soni.
Masalan, algoritm 2n ta qadam bajaradigan algoritm kirish hajmi n bo‘lganda superko‘phadli vaqtni (aniqrog‘i, eksponensial vaqtni) talab qiladi.
Eksponensial resurslardan foydalanadigan algoritm, shubhasiz, superko‘phadli hisoblanadi, biroq ayrim algoritmlar superko‘phadli bo‘lsa-da, bu xususiyat ularda juda sust namoyon bo‘ladi. Masalan, Adleman–Pomerans–Rumeli tub sonlik testi quyidagi vaqtda ishlaydi: nO(log log n), n-bitli kirish ma’lumotlarida. Bu funksiya yetarlicha katta n uchun istalgan ko‘phaddan tezroq o‘sadi, ammo kichik darajali ko‘phad ustun kelmasligi uchun kirish hajmi juda katta bo‘lishi kerak.
Superko‘phadli vaqt talab qiladigan algoritm murakkablik sinfi P dan tashqarida joylashadi.. Kobem tezisi[inglizcha] bunday algoritmlar amaliy emasligini ta’kidlaydi va ko‘p hollarda bu haqiqatan ham shunday. P va NP sinflarining tengligi muammosi hal etilmaganligi sababli, NP-to‘liq masalalarni ko‘phadli vaqtda yechadigan algoritmlar hozircha ma’lum emas.
Kvaziko‘phadli vaqt
Kvaziko‘phadli vaqtda ishlaydigan algoritmlar — ko‘phadli vaqtdagidan sekinroq, ammo eksponensial vaqt algoritmlarichalik sekin bo‘lmagan algoritmlardir. Kvaziko‘phadli algoritmning eng yomon holatdagi ishlash vaqti biror o‘zgarmas uchun c. Butun sonlarni ko‘paytuvchilarga ajratishning mashhur klassik algoritmi — umumiy son maydoni elagi usuli, u taxminan , vaqtda ishlaydi, ammo kvaziko‘phadli vaqt algoritmi emas, chunki uning ishlash vaqtini biror o‘zgarmas uchun c ko‘rinishida ifodalab bo‘lmaydi. Agar kvaziko‘phadli vaqt ta’rifidagi «c» doimiysi 1 ga teng bo‘lsa, ko‘phadli vaqt algoritmiga ega bo‘lamiz; agar u 1 dan kichik bo‘lsa, subchiziqli vaqt algoritmiga ega bo‘lamiz.
Kvaziko‘phadli vaqt algoritmlari odatda NP-qiyin masalani boshqa masalaga keltirishda yuzaga keladi. Masalan, 3SAT kabi NP-qiyin masalani B masalasiga keltirish mumkin, biroq bunda masala hajmi ga teng bo‘ladi. Bunday keltirish B masalasining NP-qiyinligini isbotlamaydi; u faqat 3SAT (va demak, barcha NP masalalari) uchun kvaziko‘phadli algoritm mavjud bo‘lmasa, B masalasi uchun ko‘phadli algoritm mavjud emasligini ko‘rsatadi. Xuddi shuningdek, kvaziko‘phadli vaqt algoritmlari ma’lum bo‘lgan, ammo ko‘phadli vaqt algoritmlari noma’lum ayrim masalalar ham mavjud. Bunday masalalar yaqinlashtirish algoritmlarida uchraydi. Mashhur misol — yo‘naltirilgan Shtayner masalasi bo‘lib, u uchun yaqinlashtirish koeffitsiyenti bo‘lgan kvaziko‘phadli yaqinlashtirish algoritmi mavjud (bu yerda n — uchlar soni), biroq ko‘phadli vaqt algoritmining mavjudligi ochiq muammo bo‘lib qolmoqda.
Murakkablik sinfi QP kvaziko‘phadli vaqt algoritmlariga ega barcha masalalardan iborat. Uni DTIME[inglizcha] orqali quyidagicha aniqlash mumkin:
NP-to‘liq masalalar bilan bog‘liqligi
Hisoblash murakkabligi nazariyasidagi hal etilmagan masala — P va NP sinflarining tengligi — NP sinfidagi barcha masalalarni ko‘phadli vaqtda yechadigan algoritmlar mavjud yoki yo‘qligini so‘raydi. NP-to‘liq masalalar, masalan, 3SAT uchun ma’lum bo‘lgan barcha algoritmlar eksponensial vaqt talab qiladi. Bundan tashqari, ko‘plab tabiiy NP-to‘liq masalalar uchun subeksponensial vaqtda ishlaydigan algoritmlar mavjud emas, degan faraz bor. Bu yerda «subeksponensial vaqt» quyida keltirilgan ikkinchi ta’rif ma’nosida ishlatilgan. (Boshqa tomondan, qo‘shnichilik matritsalari orqali tabiiy ravishda ifodalangan graf nazariyasidagi ko‘plab masalalarni subeksponensial vaqtda yechish mumkin, chunki kirish hajmi uchlar sonining kvadratiga teng.) k-SAT masalasi uchun bu faraz eksponensial vaqt gipotezasi[inglizcha] deb ataladi. U NP-to‘liq masalalar uchun kvaziko‘phadli vaqt algoritmlari mavjud emasligini taxmin qilgani sababli, yaqinlashtirish algoritmlari sohasidagi ayrim yaqinlashtirib bo‘lmaslik natijalari NP-to‘liq masalalar uchun kvaziko‘phadli vaqt algoritmlari mavjud emasligiga tayanadi. Masalan, to‘plamni qoplash masalasining yaqinlashtirib bo‘lmasligi bo‘yicha mashhur natijalarini ko‘ring..
Subeksponensial vaqt
Atama «subeksponensial[inglizcha] vaqt» algoritmning bajarilish vaqti istalgan ko‘phaddan tezroq o‘sishi, biroq eksponensial o‘sishdan sezilarli darajada sekinroq qolishini ifodalash uchun ishlatiladi. Shu ma’noda, subeksponensial vaqtda ishlaydigan algoritmlarga ega masalalarni faqat eksponensial vaqt algoritmlari bilan yechiladigan masalalarga qaraganda osonroq yechish mumkin. «Subeksponensial» tushunchasining aniq ta’rifi hozircha umumiy qabul qilinmagan; quyida eng ko‘p qo‘llanadigan ikkita ta’rif keltiriladi.
Birinchi ta’rif
Masala subeksponensial vaqtda yechiladi, agar uni yechadigan algoritmning ishlash vaqti logarifmi istalgan berilgan ko‘phaddan sekinroq o‘ssa. Aniqroq aytganda, har qanday ε > 0 uchun masalani O(2nε) vaqtda yechadigan algoritm mavjud bo‘lsa, masala subeksponensial vaqtga ega hisoblanadi. Bunday masalalarning barchasi murakkablik sinfi SUBEXP bo‘lib, uni DTIME orqali quyidagicha ifodalash mumkin:
Bu yerda ε kirish ma’lumotlarining bir qismi emasligini va har bir ε uchun masalani yechadigan alohida algoritm mavjud bo‘lishi mumkinligini ta’kidlash lozim.
Ikkinchi ta’rif
Ayrim mualliflar subeksponensial vaqtni 2o(n) ko‘rinishidagi ishlash vaqti sifatida ta’riflaydi. Bu ta’rif birinchi ta’rifga qaraganda ko‘proq ishlash vaqtiga yo‘l qo‘yadi. Bunday subeksponensial vaqt algoritmiga butun sonlarni ko‘paytuvchilarga ajratishning mashhur klassik algoritmi — umumiy son maydoni elagi usuli, u taxminan vaqtda ishlaydi; bu yerda kirish uzunligi n ga teng. Yana bir misol — graflar izomorfizmi masalasi[inglizcha] uchun ma’lum algoritm bo‘lib, uning ishlash vaqti .
Uchlar soni yoki qirralar soni bo‘yicha algoritm subeksponensial hisoblanishi o‘rtasida farq borligini ta’kidlash kerak. Parametrli murakkablik[inglizcha] nazariyasida bu farq , qaror masalasi va k. SUBEPT — barcha parametrli masalalar sinfi bo‘lib, ular k bo‘yicha subeksponensial va n:
bo‘yicha ko‘phadli vaqtda ishlaydi. Aniqroq aytganda, SUBEPT barcha parametrli masalalar sinfi bo‘lib, ular uchun hisoblanuvchi funksiya bilan hamda L masalasini quyidagi vaqtda yechadigan algoritm mavjud:.
Eksponensial vaqt gipotezasi
Eksponensial vaqt gipotezasi (ETH) shuni ta’kidlaydiki, 3-SAT, Bul formulalarining bajariluvchanligi masalasi kon’yunktiv normal shaklda va har bir klausulada ko‘pi bilan uchta literal bo‘lgan n ta o‘zgaruvchili formulalar 2o(n). Aniqroq aytganda, gipotezaga ko‘ra, shunday doimiy son c > 0 mavjudki, 3-SAT ni 2cn vaqt ichida istalgan deterministik Tyuring mashinasida yechib bo‘lmaydi. Agar m klausulalar sonini deb belgilasak, ETH quyidagi farazga teng kuchli: k-SAT ni 2o(m) vaqt ichida yechib bo‘lmaydi, bunda k ≥ 3 bo‘lgan har qanday butun son uchun o‘rinli. Eksponensial vaqt gipotezasidan P ≠ NP kelib chiqadi, biroq uning inkoridan P = NP degan xulosa kelib chiqmaydi.
2026-yil oktabr oyida sun’iy intellekt bilan shug‘ullanuvchi AQSh kompaniyalari — OpenAI va Anthropic — shuni e’lon qildiki, katta til modellari ETH gipotezasini rad etganini, subeksponensial vaqtda ishlashi aytilayotgan aniq algoritmlarni namoyish qilganini e’lon qildi. ETH gipotezasini shakllantirgan olimlar ham kirgan ekspertlar guruhi ushbu ishni tekshirish uchun hamkorlik boshlaganini ma’lum qildi.
Eksponensial vaqt
Algoritm eksponensial vaqtda ishlaydi, agar T(n) qiymati yuqoridan 2poly(n), bu yerda poly(n) — n o‘zgaruvchili biror ko‘phad. Aniqroq aytganda, algoritm eksponensial vaqtda ishlaydi, agar T(n) qiymati O(2nk) bilan chegaralangan; bu yerda doimiy k. Deterministik Tyuring mashinalarida eksponensial vaqtda bajariladigan masalalar murakkablik sinfini tashkil etadi: EXP.
Ba’zan eksponensial vaqt atamasi ishlash vaqti T(n) = 2O(n), bunda ko‘rsatkich n ning chiziqli funksiyasidan oshmaydi. Bu murakkablik sinfiga olib keladi: E[inglizcha].
Ikki karra eksponensial vaqt
Algoritm ikki karra eksponensial[inglizcha] vaqtda ishlaydi, agar T(n) qiymati yuqoridan 22poly(n), bu yerda poly(n) — n o‘zgaruvchili biror ko‘phad. Bunday algoritmlar murakkablik sinfiga kiradi: 2-EXPTIME[inglizcha].
Ma’lum bo‘lgan ikki karra eksponensial algoritmlarga quyidagilar kiradi:
- Hisoblash protsedurasi Presburger arifmetikasida
- Hisoblash Gröbner bazisini (eng yomon holatda)
- Haqiqiy yopiq maydonlardagi kvantorlarni yo‘qotish kamida ikki karra eksponensial bajarilish vaqtini talab qiladi va shu vaqt ichida bajarilishi mumkin.