1. Dasturiy ta’minot va uning turlari


Tez tartiblash algoritmida biz asosan ikkita funktsiyani qo'llaymiz: -



Download 14,99 Mb.
bet14/89
Sana22.07.2022
Hajmi14,99 Mb.
#838566
1   ...   10   11   12   13   14   15   16   17   ...   89
Bog'liq
Gost 2022

Tez tartiblash algoritmida biz asosan ikkita funktsiyani qo'llaymiz: - Split() - pivotni tanlang va qatorni pivot atrofida aylantiring, biz oxirgi elementni pivot sifatida tanlaymiz.
-quickSortServe () - chap va o'ng ichki qismlarni rekursiv tartiblash.

Tezkor saralashning murakkabligini tahlil qilish:

Vaqtning murakkabligi


    1. Eng yaxshi holat: O (nlogn)

    2. Eng yomon holat: O (n2)

    3. O'rtacha ish: O (nlogn)




  1. Quicksort barqaror tartiblash algoritmi emas.

  2. Quicksort - bu joyida tartiblash algoritmi - yordamchi joyni talab qilmaydi.

  3. Amalda, tezkor ma'lumotlar birlashma va yig'ish tartibiga qaraganda tezroq, ma'lumotlar kichik va / yoki tashqi xotira maydonida saqlanadi.

  4. Quicksort massivlar holatida Merge sort dan yaxshiroq ishlaydi va saralash uchun qo'shimcha joy talab etilmaydi.

  5. Bundan tashqari, bu keshga mos tartiblash algoritmi, chunki u massivlar uchun ishlatilganda mos yozuvlar maydoniga ega.

  6. Shuningdek, bu quyruq rekursivdir, shuning uchun quyruqni optimallashtirish amalga oshiriladi.

  7. Bog'langan ro'yxatlarni saralash uchun Tezkor tartiblash o'rniga Birlashtirish tartibiga afzallik beriladi.





61. Graflar nazariyasi elementlari (Graf, turlari, atamalari, asosiy tushunchalari)
1736-yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg1 ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.
Graf deb shunday < V, U> juftlikka aytiladiki, bu yerda V≠Ø va U-1,v2> (v1€V, v2€V) ko‘rinishdagi juftliklar korteji1 bo‘lib, Vx V to‘plamning elementlaridan tuzilgandir. G=(V, U) graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. Graflar nazariyasida «uch» iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi. G(V,U) graf elementlarining soni (|V|+|U|) ga tengdir, bu yerda grafning uchlari soni |V|≠0 va bilan uning qirralari (yoylari) soni belgilangan.
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar (yoylar) soni ga qarab belgilanadi va bu holda grafni (m,n)- graf deb ataydilar.
Agar G(V,U) grafda kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanmagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (oriyentirlangangraf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb ataladi.
Agar G(V,U) grafning (orgrafning) korteji tarkibida V×V to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning (a,a)€U elementi sirtmoq deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi.
Umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin to‘plam va kortej faqat chekli bo‘lgan G(V,U) graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.
Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralganxolisyalong‘ochuch deb ataladi.
62. Grafni tasvirlash usullari( qo’shnilik matritsasi, binar matritsa, insidentlik matritsasi, qo’shnilik ro’yxati)

Download 14,99 Mb.

Do'stlaringiz bilan baham:
1   ...   10   11   12   13   14   15   16   17   ...   89




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