Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar


Download 305.73 Kb.
bet11/19
Sana18.06.2023
Hajmi305.73 Kb.
#1573762
1   ...   7   8   9   10   11   12   13   14   ...   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

Logarifmlar.
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:

Download 305.73 Kb.

Do'stlaringiz bilan baham:
1   ...   7   8   9   10   11   12   13   14   ...   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling