|
Algoritm orqali yechilishi mumkin bo’lgan masalalarga misollar(2)
|
səhifə | 3/4 | tarix | 17.11.2022 | ölçüsü | 0,67 Mb. | | #69565 |
|
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(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.
- 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) 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
Dostları ilə paylaş: |
|
|