Algoritmlar. O’quv-uslubiy majmua

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: