|
Reja: 1 statik va dinamik o’lchovlar
|
| bet | 2/4 | | Sana | 30.07.2023 | | Hajmi | 21.76 Kb. | | #77669 |
Bog'liq 1 Algoritm murakkabligini statik va dinamik o‘lchovlari Vaqt va Boymamatova Rayhona Abduhalil qizi, erkin-iqtisodiy-hududlarni-tashkil-etishda-jahon-tajribasi, H , 1. Пул ва банклар НЎД, KOSMONAVTIKA KUNI, kllqNsMrYUpx59jvw5Q9TAFI6iBIlR1COmUr54Nc, Mavzu Jismoniy madaniyat nazariyasi va metodikasi fan sifatida, McDonald\'s kompaniyasi, Sayyoramizni asrang!, 1701192845, EVTANAZIYA VA PALLIATIV YORDAM ETIK MUAMMOLAR SIFATIDA, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org (1), 1 Aylantiruvchi moment formulasini korsating?-fayllar.orgPolilogarifmik vaqt
Algoritm ishga kirishishi aytiladi polilogarifmik vaqt, agar T(n) = O ((log n) k), ba'zilar uchun k... Masalan, matritsalarni ko‘paytirish tartibi masalasini polilogarifmik vaqtda yechish mumkin. parallel PAM mashinasi .
Chiziqli logarifmik vaqt
Chiziqli-logarifmik - bu ko'rsatkichli kvazizikli vaqtning maxsus holati k= 1 logarifmik hadda.
Chiziqli logarifmik funktsiya shaklning funktsiyasidir n jurnal n(masalan, mahsulot chiziqli va logarifmik atamalar). Algoritm ishlashi aytiladi chiziqli-logarifmik vaqt, agar T(n) = O ( n jurnal n) ... Shunday qilib, chiziqli-logarifmik element chiziqli haddan tezroq, lekin har qanday polinomga qaraganda sekinroq o'sadi. n 1 dan qat'iy yuqori darajaga ega.
Ko'p hollarda ish vaqti n jurnal n oddiygina operatsiya natijasidir t (log n) n bir marta. Masalan, ikkilik daraxt bilan tartiblash har bir elementni n o‘lchamli massivga birma-bir kiritish orqali ikkilik daraxt hosil qiladi. Insert operatsiyasidan beri muvozanatli ikkilik qidiruv daraxti O ni oladi (log n), algoritmning umumiy bajarilish vaqti chiziqli-logarifmik bo'ladi.
Taqqoslash bo'yicha saralash hech bo'lmaganda logdan beri eng yomon holatlardagi taqqoslashlarning chiziqli jurnalini talab qiladi ( n!) = Θ( n jurnal n) Stirling formulasi bo'yicha. Xuddi shu bajarilish vaqti ko'pincha takrorlanish tenglamasidan kelib chiqadi T(n) = 2 T(n/ 2) + O ( n).
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)).
|
| |
