Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari Doimiy vaqt

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: