«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Subxponensial vaqt

Muddat subeksponent vaqt maʻlum bir algoritmning bajarilish vaqti har qanday polinomga qaraganda tezroq oʻsishi, ammo eksponentdan sezilarli darajada kamligini ifodalash uchun ishlatiladi. Shu maʻnoda, vaqtning subekspentsial algoritmlari bilan bogʻliq muammolar faqat eksponent vaqtga ega algoritmlarga qaraganda ancha yumshoqroq. "Sub-eksponent" ning aniq taʻrifi hali umuman qabul qilinmagan va biz quyida eng keng tarqalgan ikkita taʻrifni keltiramiz.

Birinchi taʻrif

Agar ish vaqti logarifmasi berilgan koʻpburchakdan kamroq oʻsadigan algoritm bilan hal qilinsa, sub-eksponent vaqt ichida muammo hal qilinadi deyiladi. Aniqrogʻi, har qanday ε\u003e 0 uchun muammoni O (2 n ε) vaqt ichida echadigan algoritm boʻlsa, muammoning subekspentsial vaqti bor. Bu kabi barcha muammolar toʻplami murakkablik sinfini tashkil etadi SUBEXP, bu DTIME atamalarida quyidagicha ifodalanishi mumkin.

SUBEXP \u003d ⋂ ε\u003e 0 DTIME (2 n ε) (\\ displaystyle (\\ text (SUBEXP)) \u003d \\ bigcap _ (\\ varepsilon\u003e 0) (\\ text (DTIME)) \\ left (2 ^ (n ^ (\\ varepsilon)) )) \\ oʻng))

Shuni esda tutingki, bu erda ε kirish maʻlumotlarining bir qismi emas va har bir ε uchun muammoni echish uchun oʻz algoritmi boʻlishi mumkin.