1-Amaliy mashg’ulot Mavzu: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi. Ishdan maqsad

Download 167,34 Kb.
bet	2/3
Sana	14.05.2024
Hajmi	167,34 Kb.
	#233492

1 2 3

Bog'liq
1-amaliy (1)

Algoritmni vaqt bo’yicha baholash
1-masala.

O “katta” modeli esa algoritmlarda takrorlanishlar soniga asoslanib algoritmlarni baholab beradi.
Misol. n! ni hisoblash algoritmini bigO modeli bilan baholang
N! ni hisoblash algoritmi quyidagicha bo’lsa,
int natija=1;
for i: 2...n
natija*=i;
natija

Algoritmni xotira bo’yicha baholash. int natija=1 da int turidagi natija o’zgaruvchisiga 1 sonini ta’minlayapmiz. Bu yerda bitta int turidagi o’zgaruvchi e’lon qilingani uchun xotiradan bir birlik (4 bayt) joy egallaydi. natija*=i; da ko’paytirish amali bajarilyapti. Bu yerda natija o’zgaruvchisi va int turidagi i o’zgaruvchisi qatnashyapti. Xotiradan yana bir birlik (4 bayt) joy egallaydi. Bizda jami ikki birlik joydan joydalandik. Masalada n sonning qiymati necha bo’lishidan qat’iy nazar bizning algoritm xotiradan ikki birlik joydan foydalanib buni amalga oshiradi. Demak, algoritmning xotira bo’yicha bahosi O(1) ga teng.
Eslatma O(c) baholashda c o’zgarmas son bo’lsa, uning bahosi O(1) ga teng bo’ladi.
Algoritmni vaqt bo’yicha baholash
Algoritmni vaqt bo’yicha baholashda unda takrorlanishlar soni e’tiborga oinadi. Bizning algoritmda n-2 ta takrorlanish bor. Bundan algoritmning vaqt bo’yicha bahosi O(n-2) bo’ladi. O “katta” baholashning xususiyatiga ko’ra O(n-2)=O(n) ga teng.
Demak, n! ni xotira bo’yicha bahosi O(1), vaqt bo’yicha bahosi O(n) ga teng
1-masala. Ko’rinishdagi kvadrat tenglama uchun algoritm va dastur tuzing. Algoritmni baholang. Bu yerda a,b,c berilgan sonlar.

2-masala. Tomonlari a,b,c ga teng bo’lgan uchburchak yuzasini Geron formulasi boyicha hisoblash algoritmi va dasturini tuzing. Algoritmni baholang.

3-masala. ko’rinishidagi tenglamaning ildizlari butun sonlar bo’lib, [-100; 100] oraliqda joylashgan bo’lsa, tenglama ildizlarini aniqlash algoritmi va dasturini tuzing.

Download 167,34 Kb.

1 2 3

Download 167,34 Kb.