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

Ikkinchi taʻrif

Baʻzi mualliflar sub-eksponent vaqtni 2 o ( n). Ushbu taʻrif birinchi taʻrifga qaraganda uzoqroq ishlashga imkon beradi. Bunday subeksponent vaqt algoritmiga misol sifatida butun sonlarni faktorlarga faktoring qilish boʻyicha taniqli klassik algoritm, umumiy sonli maydonni elakdan oʻtkazish usuli kiradi. 2 O ~ (n 1/3) (\\ displaystyle 2 ^ ((\\ tilde (O)) (n ^ (1/3)))), kirish uzunligi qaerda n... Yana bir misol - uchun taniqli algoritm grafik izomorfizm muammolariuning ish vaqti 2 O ((n log-n)) (\\ displaystyle 2 ^ (O ((\\ sqrt (()) n \\ log n)))).

Eʻtibor bering, algoritm choʻqqilar soni yoki qirralar soni boʻyicha sub-eksponensial boʻladimi. IN parametrlangan murakkablik bu farq aniq juftlik, echuvchanlik muammosi va parametrni koʻrsatish orqali mavjud k. YOʻQ subekspentsial vaqt ichida ishlaydigan barcha parametrlangan muammolarning sinfi k va polinom uchun n :

SUBEPT \u003d DTIME (2 o (k) ⋅ poly (n)). (\\ displaystyle (\\ text (SUBEPT)) \u003d (\\ text (DTIME)) \\ chap (2 ^ (o (k)) \\ cdot (\\ text (poly)) (n) \\ right).)

Aniqrogʻi, SUBEPT - bu barcha parametrlangan vazifalarning klassi (L, k) (\\ displaystyle (L, k))buning uchun hisoblanadigan funktsiya mavjud f: N → N (\\ displaystyle f: \\ mathbb (N) \\ to \\ mathbb (N)) dan f ∈ o (k) (\\ displaystyle f \\ in o (k)) va hal qiladigan algoritm L davomida $ 2 f (k) -poli (n) (\\ displaystyle 2 ^ (f (k)) \\ cdot (\\ text (poly)) (n)) $.

Algoritm samaradorligini baholash uchun eng muhim koʻrsatkichlar:

Algoritmni bajarish vaqti, - kerakli RAM miqdori.

Hozirgi kunda yarim asrlik texnik taraqqiyot tufayli birinchi koʻrsatkich (bajarish vaqti) koʻpincha ikkinchisiga qaraganda ancha muhimroq, shuning uchun biz faqat shu haqida toʻxtalamiz.