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



Download 101,89 Kb.
bet3/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

Lineer vaqt
chiziqli vaqt, yoki O ( nagar uning murakkabligi O bo'lsa ( n). Norasmiy ravishda, bu etarli darajada katta kirish hajmi uchun ish vaqti kirish hajmi bilan chiziqli ravishda oshib borishini anglatadi. Masalan, ro'yxatning barcha elementlarini jamlaydigan protsedura ro'yxat uzunligiga proportsional vaqtni oladi. Ushbu tavsif to'liq aniq emas, chunki ish vaqti aniq proportsionallikdan sezilarli darajada farq qilishi mumkin, ayniqsa kichik qiymatlar uchun. n.
Chiziqli vaqt ko'pincha algoritmning kerakli atributi sifatida qaraladi. (deyarli) chiziqli ish vaqti yoki undan yuqori bo'lgan algoritmlarni yaratish uchun ko'plab tadqiqotlar o'tkazildi. Ushbu tadqiqotlar dasturiy ta'minot va apparat yondashuvlarini o'z ichiga oladi. Uskunani bajarish holatida, standart hisoblash modellarida matematik jihatdan hech qachon chiziqli bajarish vaqtiga erisha olmaydigan ba'zi algoritmlar chiziqli vaqtda ishlashi mumkin. Ushbu maqsadga erishish uchun parallellikdan foydalanadigan ba'zi apparat texnologiyalari mavjud. Masalan, assotsiativ xotira. Ushbu chiziqli vaqt tushunchasi Boyer-Mur algoritmi va Ukkonen algoritmi kabi qatorlarni taqqoslash algoritmlarida qo'llaniladi.
Kvazilinear vaqt
Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T(n) = O ( n jurnal k nba'zi doimiy uchun k... Chiziqli-logarifmik vaqt bilan alohida holat k= 1. Zaif-O belgilaridan foydalanilganda, bu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n 1 + e) ​​har qanday e> 0 uchun va har qanday polinomdan tezroq ishlaydi n
Yuqorida aytib o'tilgan chiziqli-logarifmik algoritmlarga qo'shimcha ravishda, kvaziziiqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:

  • O'z joyida birlashtirish tartibi, O ( n jurnal 2 n)

  • Tez tartiblash, O ( n jurnal n), ehtimolli versiyada eng yomon holatda chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti mavjud.

  • Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni

  • Tez Furye o'zgarishi, O ( n jurnal n)

  • Monge matritsalarini hisoblash, O ( n jurnal n)


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