|
3-kurs sirtqi kompyuter injeneringi yo`nalishi 961-20 guruh talabasi babadjanova ozodaning algaritmlarni loyihalash fanidan yozgan
|
| bet | 11/19 | | Sana | 15.05.2024 | | Hajmi | 83,36 Kb. | | #235490 |
Bog'liq 1 Algoritm murakkabligini statik va dinamik o‘lchovlari Vaqt vaLogarifmlar.
2.3. Rekursiya.
Algoritmik tuzilmalarni joylashtirish tufayli rekursiv algoritmlarning murakkabligini baholash oson emas.
f(n) Þ f(n* f(n-1))
Masalan, n algoritmini rekursiv baholash uchun! Murakkablik rekursiyaga kiritilgan har bir algoritmning murakkabligiga bog'liq bo'ladi.
Umuman T(n) ~ O(N).
Boshqa rekursiv algoritmlar odatda vaqt murakkabligiga ega T(n) ~ O(a) , qayerda a= const, bu bir xil masalani yechish uchun rekursiv bo'lmagan algoritmning murakkabligidan kattaroq umumiy murakkablikka olib keladi.
2.4 Algoritm va dasturlarning murakkabligini baholash.
2.4.2 Bog'liqlikni tiklash algoritmlari.
Ba'zi hollarda dasturning tuzilishi noma'lum va siz faqat turli o'lchamdagi kirish ma'lumotlari uchun uning ishlash vaqtini aniqlashingiz mumkin. T(N) (sek.)
Dasturning, funksiyaning murakkabligining analitik bog'liqligini qurish T(N) ba'zi bir intervalda [ Nmin, Nmax] ... Keyinchalik, ba'zi bir analitik funktsiyaning topilgan egri chizig'i funksiya parametrlarining o'zgarishi va yaqinlashish xatosining taxmini bilan yaqinlashtiriladi.
Qoida tariqasida, vaqt murakkabligining taniqli funktsiyalari bunday funktsiya sifatida ishlatiladi: O(n!), O(XN), O(NX), O(logN), O(https://pandia.ru/text/78/183/images/image010_72.gif "width =" 307 "height =" 225 src = "> Dasturda o'tkazilgan tajriba natijasida vaqt qiyinchiliklari jadvali tuzildi. olingan:
Funktsiyaning yaqinlashishini izlash natijasida quyidagi analitik bog'liqlik olindi:
https://pandia.ru/text/78/183/images/image012_68.gif "kenglik =" 321 "balandlik =" 143 src = ">
2-misol:
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
3-kurs sirtqi kompyuter injeneringi yo`nalishi 961-20 guruh talabasi babadjanova ozodaning algaritmlarni loyihalash fanidan yozgan
|
