Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar


Algoritm Ma’lumotlar tuzilmasi



Download 30,55 Kb.
bet8/8
Sana31.01.2021
Hajmi30,55 Kb.
#58040
1   2   3   4   5   6   7   8
Bog'liq
Laboratoriya 1 - AL

Algoritm

Ma’lumotlar tuzilmasi

Vaqt bo’yicha murakkabligi

Qo’shimcha ma’lumotlar







Yaxshi

O’rta

Yomon

Yomon holatda

Tezkor saralash

Massiv

O(n log(n))

O(n log(n))

O(n2)

O(n)

Surish orqali saralash

Massiv

O(n log(n))

O(n log(n))

O(n log(n))

O(n)

Piramidali saralash

Massiv

O(n log(n))

O(n log(n))

O(n log(n))

O(1)

Pufakchali saralash

Massiv

O(n)

O(n2)

O(n2)

O(1)

Qo’yish orqali saralash

Massiv

O(n)

O(n2)

O(n2)

O(1)

Tanlash orqali saralash

Massiv

O(n2)

O(n2)

O(n2)

O(1)

Blokli saralash

Massiv

O(n+k)

O(n+k)

O(n2)

O(nk)

Razryad bo’yicha saralash

Massiv

O(nk)

O(nk)

O(nk)

O(n+k)

Qidirish algoritmlari tahlili:

Algoritm

Ma’lumotlar tuzilmasi

Vaqt bo’yicha murakkablik

Xotira bo’yicha murakkabligi






O’rta

Yomon

Yomon

Chuqurlik bo’yicha qidirish (DFS)

|V| tepalik va |E| bog’lovchili graf

-

O(|E|+|V|)

O(|V|)

Kenglik bo’yicha qidirish (BFS)

|V| tepalik va |E| bog’lovchili graf

-

O(|E|+|V|)

O(|V|)

Binar qidirish

n elementdan iborat saralangan massiv

O(log(n))

O(log(n))

O(1)

Chiziqli qidirish

Massiv

O(n)

O(n)

O(1)

Deykstraning algoritmi bo’yicha ustuvor navbatlar (двоичная куча)dan foydalangan holda qisqa masofani toppish

|V| tepalik va |E| bog’lovchili graf

O((|V|+|E|)log|V|)

O((|V|+|E|)log|V|)

O(|V|)

Deykstraning algoritmi bo’yicha ustuvor navbatlar sifatida massivdan foydalangan holda qisqa masofani toppish

|V| tepalik va |E| bog’lovchili graf

O(|V|2)

O(|V|2)

O(|V|)

Bellman-Ford algoritmidan foydalangan holda qisqa masofani topish

|V| tepalik va |E| bog’lovchili graf

O(|V| |E|)

O(|V| |E|)

O(|V|)

TOPSHIRIQ

1 – topshiriq.

Berilgan variant bo’yicha C++ (Python, Java) tilida har uchala saralash metodini bajaring va jadval shaklida solishtirib analiz qiling.

Birinchi topshiriq bo’yicha variantlar

Ro’yhat bo’yicha variant nomeri

Massivni to’ldirish

Saralash metodi

Har bir metod uchun massivdagi elementlarning soni

1,2,3

Tasodifiy elementlar bilan to’ldirilgan massiv

Sanash

Pufakchali

Shell


300

1200

4000

4,5,6

Tasodifiy elementlar bilan to’ldirilgan massiv

Surish

Tezkor


Tanlash

400

1300

4500

7,8,9

Tasodifiy elementlar bilan to’ldirilgan massiv

Pufakchali

Tezkor


Kiritish

200

1500

4000

10,11,12

Tasodifiy elementlar bilan to’ldirilgan massiv

Surish

Sheyker


Tezkor

500

1600

5000

13,14,15

Tasodifiy elementlar bilan to’ldirilgan massiv

O’rniga qo’yish

Pufakchali

Tanlash


350

2000

6000

16,17,18

Tasodifiy elementlar bilan to’ldirilgan massiv

Sheyker

Tezkor


Surish

450

1800

5500

2 – topshiriq

C++ (Python, Java) tilida quyida keltirilgan amallarni bajargan holda ustuvor navbat tashkil qiling:



  • Berilgan N ta elementdan iborat ustuvor navbat hosil qiling;

  • Yangi element qo’shing;

  • Eng katta elementni yechib oling;

  • Berilgan qandaydir elementning prioritetini o’zgartiring;

  • Berilgan qandaydir elementni yechib oling;

  • Ikkita ustuvor navbatni birlashtiring.

Nazorat savollari:

  1. Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi?

  2. Vaqt bo’yicha murakkablikda yaxshi va yomon holatlar bir xil bo’lishi mumkinmi? Xulosangizni misollar orqali tushuntiring.

  3. Rekursiv algoritmlarning murakabligini baholashning asosi nimada?

  4. Musbat butun son uchun faktorialni hisoblashning rekursiv va iteratsion usullarini vaqt bo’yicha murakkabligini baholang. Har bir holat uchun murakkablik sinfini aniqlang. Natijani tushuntiring.

Adabiyotlar ro’yhati:

  1. Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.

  2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.

  3. Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.

  4. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.

  5. Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.

Download 30,55 Kb.

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




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