1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Subeksponensial vaqt

Muddati subeksponensial vaqt ba'zi algoritmlarning bajarilish vaqti har qanday ko'phadga qaraganda tezroq o'sishi mumkinligini ifodalash uchun ishlatiladi, lekin u eksponensialdan sezilarli darajada kamroq bo'lib qoladi. Shu ma'noda, subeksponensial vaqt algoritmlari bilan bog'liq muammolar faqat eksponensial vaqtli algoritmlarga qaraganda ancha moslashuvchan. "Sub-eksponensial" ning aniq ta'rifi hali umumiy qabul qilinmagan va biz quyida eng keng tarqalgan ikkita ta'rifni keltiramiz.

Birinchi ta'rif

Agar muammo ish vaqtining logarifmi har qanday berilgan ko‘phaddan kamroq o‘sadigan algoritm bilan yechilsa, muammo subeksponensial vaqtda yechilgan deyiladi. Aniqroq qilib aytadigan bo'lsak, har qanday e> 0 uchun muammoni O (2 n e) vaqtida hal qiluvchi algoritm mavjud bo'lsa, masala subeksponensial vaqtga ega bo'ladi. Bunday masalalarning barchasi murakkablik sinfini tashkil qiladi SUBEXP, bu DTIME jihatidan ifodalanishi mumkin.

SUBEXP = ⋂ e> 0 DTIME (2 n e) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ chap (2 ^ (n ^ (\ varepsilon) ))) \ to'g'ri))

E'tibor bering, bu erda e kiritilgan ma'lumotlarning bir qismi emas va har bir e uchun muammoni hal qilishning o'ziga xos algoritmi bo'lishi mumkin.

Ikkinchi ta'rif

Ba'zi mualliflar subeksponensial vaqtni ish vaqti sifatida belgilaydilar 2 o ( n). Ushbu ta'rif birinchi ta'rifdan ko'ra uzoqroq ishlashga imkon beradi. Bunday subeksponensial vaqt algoritmiga misol sifatida butun sonlarni omillarga ajratishning mashhur klassik algoritmi, taxminan 100 ga yaqin vaqtni tashkil etadigan umumiy sonli maydon elak usulini keltirish mumkin. 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3))), kirishning uzunligi qaerda n... Yana bir misol uchun mashhur algoritm Grafik izomorfizm masalalari kimning ish vaqti 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).

E'tibor bering, bu algoritm cho'qqilar sonida yoki qirralarning sonida sub-eksponensial bo'ladimi, farq qiladi. V parametrlangan murakkablik bu farq juftlik, echilish muammosi va parametrni ko'rsatish orqali aniq namoyon bo'ladi k. SUBEPT yilda subeksponensial vaqtda bajariladigan barcha parametrlangan masalalar sinfidir k va polinom uchun n :

SUBEPT = DTIME (2 o (k) ⋅ poli (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ chap (2 ^ (o (k)) \ cdot (\ matn (poli)) (n) \ o'ng).)

Aniqroq aytganda, SUBEPT barcha parametrlangan vazifalar sinfidir (L, k) (\ displaystyle (L, k)) buning uchun hisoblash funktsiyasi mavjud f: N → N (\ displaystyle f: \ mathbb (N) \ to \ mathbb (N)) Bilan f ∈ o (k) (\ displaystyle f \ in o (k)) va hal qiluvchi algoritm L davomida 2 f (k) ⋅ poli (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ matn (poli)) (n)).