Algoritmning vaqt murakkabligi

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 n0, shundayki, uzunligi n>n0 bo‘lgan barcha kirish ma’lumotlari uchun algoritmning ishlash vaqti 5n3+3n dan oshmaydi; demak, bu algoritmning vaqt murakkabligini asimptotik ravishda quyidagicha baholash mumkin: O(n3).

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 O(1). 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 T(n) va u kirish uzunligi n 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, T(n)∈O(n) qiymatli algoritm chiziqli vaqtli algoritm deb ataladi; , algoritm esa T(n)∈O(nα)biror α>1 darajali ko‘phad bilan chegaralangan vaqtda ishlaydi; u ko‘phadli.

Vaqt murakkabligi sinflari jadvali

Quyidagi jadvalda eng ko‘p uchraydigan murakkablik sinflari. Jadvalda poly(x) ixtiyoriy ko‘phadni bildiradi, xya’ni poly(x)=xO(1).

NomiMurakkablik sinfiIshlash vaqti, T(n)Ishlash vaqtiga misollarAlgoritmlarga misollar
doimiy vaqtO(1)10Butun sonning juft yoki toqligini aniqlash (ikkilik ko‘rinishda ifodalangan)
Akkerman funksiyasining teskari funksiyasiO(α(n))Amortizatsion tahlil har bir amal uchun, o‘zaro kesishmaydigan to‘plamlar
iteratsion logarifmik vaqtO(log∗n)Sikllarni taqsimlangan ranglash
ikki karra logarifmikO(log⁡log⁡n)Chegaralangan prioritet navbatidan foydalanganda bitta amal uchun amortizatsiyalangan vaqt[inglizcha]
logarifmik vaqtDLOGTIME[inglizcha]O(log⁡n)log⁡n, log⁡n2Ikkilik qidiruv
polilogarifmik vaqtpoly(log⁡n)(log⁡n)2
subchiziqli vaqtO(nc) uchun 0<c<1n1/2, n2/3Qidirish k-o‘lchamli daraxtda
chiziqli vaqtO(n)nEng kichik yoki eng katta elementni saralanmagan massivdan qidirish
«n log-yulduzcha n»O(nlog∗n)Algoritm ko‘pburchakni triangulyatsiyalash Zaydel[inglizcha].
chiziqli-logarifmik vaqtO(nlog⁡n)nlog⁡n, log⁡n!Eng tez taqqoslashga asoslangan saralash[inglizcha]
kvadratik vaqtO(n2)n2Pufakchali saralash, qo‘shish orqali saralash, to‘g‘ridan-to‘g‘ri konvolyutsiya
kubik vaqtO(n3)n3Ikki matritsani oddiy ko‘paytirish ikkita n×n matritsaning ko‘paytmasi. Qisman korrelyatsiyani hisoblash[inglizcha].
ko‘phadli vaqtP2O(log⁡n)=poly(n)n, nlog⁡n, n10Karmarkar algoritmi uchun chiziqli dasturlash, AKS tub sonlik testi
kvaziko‘phadli vaqtQP2poly(log⁡n)nlog⁡log⁡n, nlog⁡nMa’lum bo‘lgan eng tez O(log2n) — yaqinlashtirish algoritmi yo‘naltirilgan Shtayner masalasi.
subeksponensial vaqt
(birinchi ta’rif)
SUBEXPO(2nε) barcha ε>02log⁡nlog⁡log⁡nNazariy farazlarni qabul qilsak, BPP SUBEXP sinfiga kiradi.
subeksponensial vaqt
(ikkinchi ta’rif)
2o(n)2n1/3Eng tez ma’lum algoritmlar butun sonlarni ko‘paytuvchilarga ajratish va graflar izomorfizmi[inglizcha]
eksponensial vaqt
(chiziqli eksponent bilan)
E[inglizcha]2O(n)1.1n, 10nYechish: sayohatchi sotuvchi masalasi yordamida dinamik dasturlash
eksponensial vaqtEXPTIME2poly(n)2n, 2n2Yechish: matritsalarni ko‘paytirish tartibi masalasi yordamida to‘liq qidiruv
faktorial vaqtO(n!)n!Yechish: sayohatchi sotuvchi masalasi to‘liq qidiruv orqali
ikki karra eksponensial vaqt2-EXPTIME[inglizcha]22poly(n)22nBerilgan mulohazaning to‘g‘riligini Presburger arifmetikasida tekshirish
Yevklid algoritmi log(min⁡(a,b))
Polig–Hellman algoritmi O(∑i=1sαi(log⁡p+qi)) Agar p−1 sonning ajratiladigan ko‘paytuvchilari yetarlicha kichik bo‘lsa, algoritm juda samarali ishlaydi
Pollardning ρ-usuli p1/2 Murakkablikning evristik bahosiga ega

Doimiy vaqt

Algoritm doimiy vaqtli algoritm deb ataladi (ishlash vaqti O(1) ko‘rinishida yoziladi), agar T(n) 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, O(n). 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, a va b qiymatlarini a≤b qiymati hosil bo‘ladigan tarzda almashtirish» masalasi doimiy vaqtli hisoblanadi, garchi algoritmning ishlash vaqti a≤b tengsizlik bajarilganmi yoki yo‘qmi, shunga bog‘liq bo‘lishi mumkin. Biroq shunday t doimiy son mavjudki, masalani bajarish vaqti hech qachon oshmaydi t.

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 T(n) qiymati O(α) ga teng bo‘lsa, bu yerda α — doimiy son, bu T(n) qiymatiga teng bo‘lishi bilan ekvivalent.O(1).

Logarifmik vaqt

Algoritm logarifmik vaqtda, agar T(n)=O(log⁡n). Kompyuterlarda ikkilik sanoq tizimi, logarifm asosi sifatida logarifm ishlatiladi 2 (ya’ni log2n). Biroq logarifm asosini almashtirganda logan va logbn faqat o‘zgarmas ko‘paytuvchiga farq qiladi logba, u katta O notatsiyasida hisobga olinmaydi. Shunday qilib, O(log⁡n) 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.

O(log⁡n) yordamida uchraydi. Hajmi n 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. DUnda n ta so‘z alifbo tartibida saralangan deb faraz qilaylik. Bunda barcha so‘zlarning uzunligi O(1) ga teng va lug‘atning istalgan elementiga indeks orqali doimiy vaqtda murojaat qilish mumkin deb hisoblaymiz. Faraz qilaylik, D(k) — bu k-lug‘at elementi bo‘lsin. Shunda ω so‘zining lug‘atda bor-yo‘qligini O(log⁡n) vaqt ichida tekshirish mumkin. Buning uchun lug‘atning D(⌊n/2⌋) elementini ko‘rib chiqish kerak; bu yerda ⌊ ⌋ quyidagini bildiradi: sonni pastga qarab yaxlitlash. Agar D(⌊n/2⌋)<ω 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 T(n)=O(logkn) biror k. Masalan, matritsalarni ko‘paytirish tartibi masalasi bunday vaqtda yechilishi mumkin parallel RAM mashinasida[inglizcha].

Subchiziqli vaqt

Algoritm subchiziqli vaqtda ishlaydi, agar T(n)=o(n). Xususan, bunga yuqorida keltirilgan vaqt murakkabligiga ega algoritmlar, shuningdek, masalan, Grover qidiruvi (murakkabligi O(n1/2).

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 log⁡n 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 b1,…,bk ko‘rinishidagi oqim uchun algoritm O(1) vaqt ichida bi istalgan i.

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 O(n) vaqtida ishlaydi, agar uning murakkabligi O(n) 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 n.

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 T(n)=O(nlogkn) biror doimiy k. k=1 bo‘lganda, chiziqli-logarifmik vaqt deyiladi. soft-O notatsiyasida bunday ishlash vaqti O~(n) ko‘rinishida yoziladi. Kvazichiziqli vaqt algoritmlari uchun quyidagi baho ham o‘rinli: T(n)∈o(n1+ε) har qanday ε>0. Demak, bu algoritmlar n darajasi 1.

dan katta bo‘lgan istalgan ko‘phaddan tezroq ishlaydi. Yuqorida aytib o‘tilgan chiziqli-logarifmik algoritmlardan tashqari, kvazichiziqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:

Chiziqli-logarifmik vaqt

Chiziqli-logarifmik vaqt kvazichiziqli vaqtning xususiy holi bo‘lib, logarifmik ko‘paytuvchining darajasi k=1 ga teng.

Chiziqli-logarifmik funksiya — bu ko‘rinishdagi funksiya nlog⁡n (ya’ni chiziqli va logarifmik hadlarning ko‘paytmasi). Algoritm chiziqli-logarifmik vaqtda ishlaydi, agar T(n)=O(nlog⁡n). Shunday qilib, chiziqli-logarifmik funksiya chiziqli funksiyadan tezroq, ammo darajasi n dan katta bo‘lgan 1.

istalgan ko‘phaddan sekinroq o‘sadi. Ko‘p hollarda ishlash vaqti nlog⁡n shunchaki n marta bajariladigan, ishlash vaqti O(log⁡n) bo‘lgan amal natijasi bo‘ladi. Masalan, ikkilik daraxt yordamida saralash algoritmi ikkilik daraxt ni hajmi n bo‘lgan massivning har bir elementini navbatma-navbat unga kiritish orqali hosil qiladi. Muvozanatlangan ikkilik qidiruv daraxtiga[inglizcha] element kiritish amali O(log⁡n) 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 n bo‘lgan va elementlar tartibini bir qiymatli belgilaydigan o‘rin almashtirish hosil bo‘ladi. Jami n! 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 log⁡n!∼nlog⁡n 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 O(nlog⁡n) 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 T(n)=T(n/2)+O(n).

Subkvadratik vaqt

Aytishlaricha, algoritm subkvadratik vaqtda ishlaydi, agar T(n)=o(n2).

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 T(n)=O(nk) biror doimiy k. 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 n algoritmi biror doimiy An2 uchun ko‘pi bilan A ta amal bajaradi. Demak, u O(n2) 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:

  1. hisoblashning arifmetik modelidagi amallar soni kirish oqimidagi butun sonlar soniga nisbatan ko‘phad bilan chegaralangan bo‘lishi; va
  2. 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 2n butun soni berilgan bo‘lsa (u Tyuring mashinasida n ga mutanosib xotira egallaydi), 22n ni takroriy darajaga oshirish yordamida n ta amal bilan hisoblash mumkin. Biroq 22n ni ifodalash uchun sarflanadigan xotira 2n 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 a va b butun soni uchun algoritmning ishlash vaqti O((log⁡ a+log⁡ b)2) ta Tyuring mashinasi qadami bilan chegaralanadi. Bu son a va b sonlarining ikkilik ko‘rinishdagi uzunligiga nisbatan ko‘phad bo‘lib, uni taxminan log⁡ a+log⁡ b 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 a va b 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 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 2O((log⁡n)c) uchun c. Butun sonlarni ko‘paytuvchilarga ajratishning mashhur klassik algoritmi — umumiy son maydoni elagi usuli, u taxminan 2O~(n1/3), vaqtda ishlaydi, ammo kvaziko‘phadli vaqt algoritmi emas, chunki uning ishlash vaqtini biror o‘zgarmas 2O((log⁡n)c) 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 2O((log⁡n)c) 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 O(log3n) 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:

QP=⋃c∈ℕDTIME(2(log⁡n)c)

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:

SUBEXP=⋂ε>0DTIME(2nε)

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 2O~(n1/3) 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 2O(nlog⁡n).

Uchlar soni yoki qirralar soni bo‘yicha algoritm subeksponensial hisoblanishi o‘rtasida farq borligini ta’kidlash kerak. Parametrli murakkablik[inglizcha] nazariyasida bu farq (L,k), qaror masalasi va k. SUBEPT — barcha parametrli masalalar sinfi bo‘lib, ular k bo‘yicha subeksponensial va n:

SUBEPT=DTIME(2o(k)⋅poly(n)).

bo‘yicha ko‘phadli vaqtda ishlaydi. Aniqroq aytganda, SUBEPT barcha parametrli masalalar sinfi bo‘lib, (L,k) ular uchun hisoblanuvchi funksiya f:ℕ→ℕ bilan f∈o(k) hamda L masalasini quyidagi vaqtda yechadigan algoritm mavjud:2f(k)⋅poly(n).

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.

EXP=⋃c∈ℕDTIME(2nc)

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].

E=⋃c∈ℕDTIME(2cn)

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].

2-EXPTIME=⋃c∈ℕDTIME(22nc)

Ma’lum bo‘lgan ikki karra eksponensial algoritmlarga quyidagilar kiradi: