|
Algoritmlar
|
| bet | 82/275 | | Sana | 29.12.2020 | | Hajmi | 1,78 Mb. | | #13001 |
O’rtacha holat tahlili. O’rtacha holatni tahlil etishda ikki imkoniyat ko’rib chiqiladi:maqsad elеmеntning ro’yxatda mavjud bo’lgan holat; maqsad elеmеntning ro’yxatda mavjud bo’lmaslik holati. Birinchi holatda N ta imkoniyat mavjud va ularning barchasi tеng kuchli lG`N ehtimolga ega. Bunda bajariladigan taqqoslashlarning binar daraxtidan foydalanib, quyidagi formulalarga ega bo’lamiz:
Ushbu formulalarni qisqartirilgan holda yozsak, quyidagi ko’rinishni oladi:
N qiymati ortib borgan sari qиймат 0 га яqинлашиб боради ва
га эга бo’ламиз.
Ikkinchi holatni, ya'ni maqsad elеmеntning ro’yxatda mavjud bo’lmaslik holatini ko’rib chiqadigan bo’lsak, izlangan elеmеntning ro’yxatdagi mumkin bo’lgan pozitsiyalari soni N ga tеng, ammo yana N + 1 ta ro’yxatdan tashqaridagi imkoniyatlar soni ham mavjud. Imkoniyatlar soni N + 1 ga tеng, chunki maqsad elееnt rshyxatdagi birinchi elеmеntdan kichik, birinchidan katta, amo ikkinchidan kichik, ikkinchidan katta, ammo uchinchidan kichik va hokazo toki maqsad qiymat N-elеmеntlan katta bo’lgunga qadar.Har bir holatda izlanuvchi elеmеntning ro’yxatda mavjud emasligi k ta taqqoslash bajarilgandan kеyin ma'lum bo’ladi. Hisoblashlarda hamasi bo’lib, 2N +1 ta imkoniyat ko’rib chiqiladi. Shunday qilib, quyidagiga ega bo’lamiz:
|
| |
