Bo’lib tashla va hukmronlik qil usuli. Kesh xotira bilan ishlash Qo’llanish muammolari



Download 493,07 Kb.
bet7/10
Sana31.12.2021
Hajmi493,07 Kb.
#236194
1   2   3   4   5   6   7   8   9   10
Bog'liq
algoritm

Amal

Murakkablik

Push(T value)

Resize()ga qarang.

Pop()

\(O(1)\)

Peek()

\(O(1)\)

IsEmpty()

\(O(1)\)

Size()

\(O(1)\)

Resize()

Eng yomon holatda \(O(n)\), o’rtacha esa \(O(1)\) vaqt oladi.

Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize()ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni vaqt murakkablikka ega deb qabul qilishimiz mumkin.


4. Misollar
Merge Sort algoritmi va uning ishlash prinsipi
"Bo'lib tashla va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir. Merge Sort algoritmi bu saralanmagan massivni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash printsipida to'liq bo'lib tashla va hukmronlik qil g'oyasini uchratish mumkin. Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

  1. Berilgan massivni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu qadam, qism massivlar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha davom etadi.

  2. Hosil bo'lgan massivlarni qaytib birlashtirib chiqish va bir vaqtning o'zida hosil bo'luvchi massiv saralangan bo'lishini ta'minlash.

Merge sort algoritmi qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e'tibor bering. Unda amallar tartibi ham ko'rsatib qo'yilgan(6.3-rasm).

Ko'rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e'tibor bergan bo'lsangiz, birinchi bo'linishdan keyingi massivning chap va o'ng qismlarida asosiy massiv bilan bir xil amal ketmoqda, ya'ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.

Merge sort algoritmi qadamlari:


  1. Merge Sort funksiyasiga massiv va uning boshlang'ich (left) va oxirgi nuqtalari (right) beriladi.

  2. Massivning o'rtasi hisoblanadi: mid = (left + right)/2. Bu uni teng ikkiga bo'lish uchun kerak bo'ladi.

  3. Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.

  4. 2- va 3-qismlarda hosil bo'lgan massivlar birlashtirib chiqiladi. (Massiv mavzusidagi ikkita massivni birlashtirish masalasini ko'rib chiqing)

Algoritm ishlash tezligi O(nlogn) bo'lib tezligi O(n²) bo'lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O'zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo'lishi isbotlangan. Merge sort turg'un saralash hisoblanadi, ya'ni saralamagan massivda bir nechta bir xil elementlar kelgan bo'lsa, ularning tartibi saralangan massivda ham o'zgarib ketib qolmaydi. Algoritm ishlashi uchun xotiradan qo'shimcha O(n) joy talab qiladi. Bo'lib tashla va hukmronlik qil paradigmasi asosida ishlaydigan eng mashhur algoritm — bu ikkilik qidirish (binary search). Ikkilik qidirish algoritmi saralangan massivdan element topishning eng samarali algoritmlaridan biri.

6.3-rasm. Merge sort algoritmining ishlash printsipi.




Download 493,07 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10




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