O’zbekiston respublikasi

Qurilish pm
Endi dastlabki hisob-kitoblar bosqichida namunaviy nomuvofiqlik jadvalini hisoblashga o'tish kifoya. Umumiylikni yo'qotmasdan, biz buni qandaydir darajada deb taxmin qilishimiz mumkin . Oldindan ishlov berish algoritmi qatorlar to'plamini quyidagi kichik to'plamlarga bo'lishdan foydalanadi:
Algoritm bosqichlardan iborat. Bosqichda , to'plamdagi qatorlar hisoblab chiqila-di , to'plam qayerda.
Ushbu jadvalni hisoblash uchun ishlatiladigan usul matnni tahlil qilish bosqichida qo'llaniladigan usulga asoslanadi. Bosqich uchun algoritmni ko'rib chiqing . Bos-qichda namunani tahlil qilish algoritmi uchun kirishlar namunaning pastki qatorlari va bu erda mos ravishda namuna va matn sifatida ko'rib chiqiladi va oldingi bosqichlarning natijalarini o'z ichiga olgan massivdir. Bosqich chiqish-lari kiritiladi .
Ushbu jadvalni hisoblash uchun ishlatiladigan usul matnni tahlil qilish bosqichida qo'llaniladigan usulga asoslanadi. Bosqich uchun algoritmni ko'rib chiqing . Bos-qichda namunani tahlil qilish algoritmi uchun kirishlar namunaning pastki qatorlari va bu erda mos ravishda namuna va matn sifatida ko'rib chiqiladi va oldingi bosqichlarning natijalarini o'z ichiga olgan massivdir. Bosqich chiqish-lari kiritiladi . Ular nomuvofiqliklarni topadigan bosqich bundan mustasno, har bir satr uchun bosqichda matnni tahlil qilish algoritmidagi kabi ga qadar emas, balki nomuvofiqliklarni topish talab qilinadi .

Qiyinchilik reytingi: Keling, matnni tahlil qilishga sarflangan vaqtni ko'rib chiqaylik. Agar protsedura chaqirilsa va chiqarib tashlansa , matnni tahlil qilish siklining har bir iteratsiyasi belgilangan vaqtni oladi va umumiy vaqtni beradi . Qo'ng'iroqlar paytida protsedura tomonidan bajariladigan operatsiyalarning umumiy soni ga teng , chunki u matnning har bir belgisini ko'pi bilan bir marta tekshiradi. Har bir chaqiruvdagi protsedura jami elementlarga ega bo'lgan va massivni qayta ishlaydi. Ishlash vaqtini ushbu kirishlarning har biri bilan belgilangan vaqtdagi operatsiyalarni bog'lash orqali hisoblash mumkin, bu har bir qo'ng'iroq uchun ga teng bo'lgan hisoblash vaqtini beradi . Shunday qilib, umumiy matnni tahlil qilish vaqti ekanligini ko'rish mumkin . Keling, qurilishni ko'rib chiqaylik . Jarayonning to'g'riligini tekshirishda ishlatiladigan argumentlarga o'xshash argumentlar yordamida shuni ko'rsatish mumkinki, bosqichda mos kelmasliklarning kerakli sonini topish uchun B sharti qondiriladigan pozitsiyalar talab qilinadi va alohida holatda, ya'ni , bosqichda , bunday lavozimlar talab qilinadi
Конец формы

Namuna tahlili bosqichlarining har bir bosqichida halqa iteratsiyalarni amalga oshiradi . Protseduralarning ishlash vaqtidan tashqari va har bir iteratsiya ma'lum vaqtni talab qiladi. Jarayon bosqichidagi barcha iteratsiyalar vaqt oladi . Ilgari, ish vaqti qidirilayotgan nomuvofiqliklar soniga mutanosib ekanligi ko'rsatilgan. Shunday qilib, har bir qo'ng'iroq vaqtni oladi , bu esa ga teng . Shunday qilib, bosqich uchun umumiy vaqt = . Barcha bosqichlarni umumlashtirib, biz umumiy hisoblash vaqtini olamiz . Shunday qilib, namunani oldindan qayta ishlash va matn tahlilini o'z ichiga olgan sarflangan umumiy vaqt ga teng .