Algoritm-1must pdf

Nazriy savol javoblari

1. Dasturdagi murakkab algoritmlar asosan funksiya va protseduralarda

bo’ladi. Keling, buni ko’rish uchun Fast hamda Slow nomli funksiyalar yaratib olaylik va bu funksiyalarning turli xil ko’rinishdagi murakkabligini baholab ko’raylik. Demak ushbu kodni ko’rib chiqamiz.

Slow funksiyasi O(N^3) murakkablikka ega bo’lib unda ichma ich 3 ta for sikli mavjud: N*N*N. Buni osonlik bilan ko’rish mumkin.
Endi Fast funksiyasini ko’radigan bo’lsak unda ichma-ich 2 ta for sikli mavjud. Ammo ikkinchi siklda biz Slow funksiyasini chaqirganmiz. Bu esa
algoritmning murakkabligini yanada oshiradi, ya’ni O(N^2) * O(N^3) = O(N^5).

Both funksiyasida biz ikkala funksiyadan ham foydalandik.

2. Algoritmlarni eng yomon va o’rtacha holatlarda baholash

Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish mashinasi ( tasodifiy - kirish mashinasi , RAM operatsiyalar parallel ijro uchun taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar qadamlar sonini anglatadi.

Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x- koordinata bo'yicha saralash ").

Qo'ng'iroq qilish ( qo'ng'iroq

qilish ) protsedurasini (ma'lum miqdordagi operatsiyalarni o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz kerak

Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi:

1. 
   Dastur algoritmining vaqt murakkabligi;
   

2. 
   Bajariladigan dasturning kompilyatsiya qilingan kodining sifati; 3.Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
   

3.