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



Download 101,89 Kb.
bet8/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   ...   4   5   6   7   8   9   10   11   ...   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

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 kSUBEPT 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)).
2-bob. Algoritmlarning murakkabligi.
2.1 Algoritmlarning vaqt va hisoblash murakkabligi.
Algoritmning vaqt murakkabligi (T(N) , qayerda N- topshiriqning o'lchami) - qadamlar bilan o'lchanadigan algoritmning bajarilish vaqti (natijaga erishish uchun bajarilishi kerak bo'lgan algoritm ko'rsatmalari). Ya'ni, bu muammoni hal qilish algoritmini tashkil etuvchi elementar operatsiyalar soni (: =,<>, =, +, -, *, /; va, yoki, emas, xor; qo'ng'iroq qilish, qaytish).
Muammoni hal qilishda kiritilgan ma'lumotlarning kombinatsiyasiga (ekvivalentligi, siyrakligi, tartibliligi va kiritilgan ma'lumotlarning boshqa xususiyatlari) bog'liq bo'lgan uch xil vaqt murakkabligi mavjud.
https://pandia.ru/text/78/183/images/image002_151.gif "kenglik =" 178 balandlik = 60 "balandlik =" 60 ">
Bo‘lyapti T(N)= C* N2 kvadrat matritsa uchun amal qiladi.
Bu holda elementar operatsiyalar "+" va "*" kombinatsiyasi hisoblanadi.
Agar asl matritsa identifikatsiya bo'lsa, biz eng yaxshi holatni olamiz.
Agar matritsada elementlarning yarmi 0, yarmi 1 bo'lsa, biz O'rtacha holatni olamiz.
Doimiy BILAN, aniq ifodalab bo'lmaydigan, tashqi omillarning algoritmlarni bajarish vaqtiga ta'sirini tavsiflaydi (kompyuter tezligi, kompilyatsiya tezligi). Shuning uchun algoritmlarning vaqt murakkabligini baholash uchun vaqt birliklaridan foydalanish mutlaqo to'g'ri emas. Bu holda matritsa-vektorni ko'paytirish algoritmining vaqt murakkabligi ga proportsional deyiladi. N2 .

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   ...   4   5   6   7   8   9   10   11   ...   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish