Algoritmlar

Algoritm orqali yechilishi mumkin bo’lgan masalalarga misollar(2)

• 4) Tekislikda n ta nuqta berilgan. Bu nuqtalarni o’z ichiga olgan eng kichik qavariq ko’pburchakni topish masalasi.

Ma’lumotlar tuzilmasi

• Ma’lumotlar tuzilmasi(data structure) – bu ma’lumotlarni ularga ruxsatni va o’zgartishni osonlashtirish uchun saqlash va tashkillashtirish usuli.
• Hech bir ma’lumot tuzilmasi universal emas va barcha maqsadlarga mos kelmaydi.

Algoritmlar texnologiya sifatida

• Tasavvur qiling agar kompyuterning xotirasi va tezligini cheksiz katta qiymatgacha oshirish mumkin.
• Bu holda algoritm kerakmi?
• Kerak.
• Chunki yechim chekli vaqtda ishlashi va to‘g'ri javob chiqarishi lozim.

Algoritmlar texnologiya sifatida(2)

• Algoritm maqsadi:
• To‘g'ri javob olish
• Qisqa vaqtda hisoblash
• Kam xotira egallash

Samaradorlik

• Bitta masalani ishlab chiqilgan algoritmlar bir-biridan effektivlik bo’yicha ko’pincha katta farq qiladi.
• Bu farq har xil qurilma va yoki dasturiy ta’minotda ishlatilganda ham katta sezilarli bo’lishi mumkin.

Samaradorlik(2)

Qo’yish orqali saralash	Birlashritish orqali saralash
c1n2	c2n logn
n2	nlogn
n	logn
n=1000000	logn~20

Misol sifatida qo’yish orqali saralash va birlashtirish orqali saralash.
n – elementlar soni
c1 va c2 lar n ga bog’liq bo’lmagan konstantalar
c1 < c2

Samaradorlik(3)

• Samaradorlikka misolni ikki kompyuterda ko`rib chiqamiz – A va B
• А — milliard amalni bajaradi
• Б — o`n million amalni bajaradi.
• A kopyuter tezligi 109 amal / s
• B kopyuter tezligi 107 amal / s
• c1=2, c2=50 bo’lsin
• A kompyuterdagi amallar: 2n2
• B kopyuterdagi amallar: 50nlogn