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
|
Adabiyotlar ro’yhati:
Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.
Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.
Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.
Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.
Xulosa:
Ustuvor navbat - bu har bir element ustuvorlik bilan bog'liq bo'lgan va uning ustuvorligiga muvofiq xizmat ko'rsatadigan navbatning maxsus turi. Agar bir xil ustuvorlikka ega elementlar yuzaga kelsa, ular navbatdagi navbatga muvofiq xizmat ko'rsatiladi.
Odatda ustunlikni belgilash uchun elementning o'zi hisobga olinadi.
Masalan, eng yuqori qiymatga ega element eng yuqori ustuvor element sifatida qabul qilinadi. Ammo, boshqa holatlarda, biz eng past ustuvor element sifatida eng past qiymatga ega elementni qabul qilishimiz mumkin. Boshqa hollarda, biz ehtiyojlarimizga qarab ustuvor vazifalarni belgilashimiz mumkin.
Do'stlaringiz bilan baham: |