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

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(n^2)	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(n^2)	O(n^2)	O(1)
Qo’yish orqali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Tanlash orqali saralash	Massiv	O(n^2)	O(n^2)	O(n^2)	O(1)
Blokli saralash	Massiv	O(n+k)	O(n+k)	O(n^2)	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.