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



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

Logarifmik vaqt
logarifmik vaqt, agar T(n) = O (log n... Kompyuterlar ikkilik tizimdan foydalanganligi sababli, logarifmning asosi sifatida 2 ishlatiladi (ya'ni log 2). n). Biroq, bilan bazani almashtirish logaritmalar log a n va jurnal b n faqat doimiy koeffitsient bilan farqlanadi, bu esa O-katta belgisida bekor qilinadi. Shunday qilib, O (log n) - logarifm asosidan qat'iy nazar, logarifmik vaqt algoritmlari uchun standart belgi.
Logarifmik vaqt algoritmlari odatda binar daraxt operatsiyalarida yoki ikkilik qidiruvdan foydalanganda topiladi.
O (log n) algoritmlari yuqori samarali hisoblanadi, chunki har bir elementning bajarilish vaqti elementlar sonining ko'payishi bilan kamayadi.
Bunday algoritmning juda oddiy misoli qatorni ikkiga bo'lish, ikkinchi yarmini yana yarmiga bo'lish va hokazo. Bu O (log n) vaqtni oladi (bu erda n - satr uzunligi, biz bu erda taxmin qilamiz console.log va str.substring doimiy vaqt talab qiladi). Bu shuni anglatadiki, nashrlar sonini ko'paytirish uchun chiziq uzunligi ikki barobarga oshirilishi kerak.
// Chiziqning o'ng yarmini rekursiv chop etish funksiyasi var o'ng = funktsiya (str) (var uzunligi = ko'cha uzunligi; // yordamchi funksiya var help = funktsiya (indeks) ( // Rekursiya: o'ng yarmini chop eting agar (indeks< length ) { // Belgilarni indeksdan satr oxirigacha chop etish konsol. log (str. substring (indeks, uzunlik)); // rekursiv chaqiruv: o'ng tomoni bilan yordamchi funksiyani chaqiring yordam (Math.ceil ((uzunlik + indeks) / 2)); )) yordam (0); )
Polilogarifmik vaqt
Algoritm ishga kirishishi aytiladi polilogarifmik vaqt, agar T(n) = O ((log nk), ba'zilar uchun k... Masalan, matritsalarni ko‘paytirish tartibi masalasini polilogarifmik vaqtda yechish mumkin. parallel PAM mashinasi .
Sublinear vaqt
Algoritm ishga kirishishi aytiladi sublinear vaqt, agar T(n) = o ( n). Xususan, bu yuqorida sanab o'tilgan vaqt murakkabligi algoritmlarini, shuningdek boshqalarni o'z ichiga oladi, masalan, Grover qidiruvi murakkabligi O ( n ½).
To'g'ri bo'lsa-da, hali ham subchiziqli vaqtda ishlaydigan odatiy algoritmlar jarayonlarni parallellashtirishdan (masalan, matritsa determinantini hisoblash uchun NC 1 algoritmida), klassik bo'lmagan hisoblashlardan (Grover qidiruvida bo'lgani kabi) yoki kafolatlangan taxminga ega bo'lgan algoritmlardan foydalanadi. kirishning tuzilishi (logarifmik vaqtda ishlaydigan, ikkilik qidiruv algoritmlari va ko'plab daraxtlarni qayta ishlash algoritmlari). Biroq, satrning birinchi log (n) bitlari tomonidan aniqlangan holatda 1 bitga ega bo'lgan barcha satrlar to'plami kabi rasmiy konstruktsiyalar kirishning har bir bitiga bog'liq bo'lishi mumkin, ammo vaqt o'tishi bilan hali ham pastki chiziqli bo'lib qoladi.
Muddati sublinear ish vaqti algoritmi odatda, yuqoridagi misollardan farqli o'laroq, an'anaviy ketma-ket mashina modellarida ishlaydigan va kirish strukturasi haqida aprior bilimni talab qilmaydigan algoritmlar uchun ishlatiladi. Biroq, ular uchun ehtimollik usullaridan foydalanishga ruxsat beriladi va undan ham ko'proq, algoritmlar eng ahamiyatsiz muammolar uchun ehtimollik bo'lishi kerak.
Bunday algoritm kirish ma'lumotlarini to'liq o'qimasdan javob berishi kerakligi sababli, bu kirish oqimida ruxsat etilgan kirish usullariga juda bog'liq. Odatda bit string oqimi uchun b 1 ,...,b k, algoritm qiymatni so'rashi mumkin deb taxmin qilinadi b i har kim uchun i.
Sublinear vaqt algoritmlari, qoida tariqasida, ehtimollikdir va faqat taxminiy echimni beradi. Sublinear ish vaqti algoritmlari tadqiqot paytida tabiiy ravishda paydo bo'ladi mulkni tekshirish.

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   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