ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH
“ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH” MAVZUSIDA TAYYORLAGAN MUNDARIJA: I-bob. Kirish .............................................................................................................. 3 II-bob. Asosiy qism .................................................................................................... 4 ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH ............................ 4 O(n log log k) optimallashtirish. ............................................................................... 9 Eng uzun ortib borayotgan qismiy ketma-ketmaketlikni qayta tiklash ................... 15 Eng uzun ortib borayotgan keyingi ketma-ketlik muammosi .................................. 15 Bizga quyidagicha masala berilgan bo’lsin: Massivi berilgan : a [ 0 .. n - 1 ] va uning n ta elementi mavjud. Ushbu ketma-ketlikda eng uzun uzunlikdagi qat'iy ortib boruvchi ketma-ketlikni topish talab qilinadi. Eng ortib boruvchi pastki ketma-ketlik (NVP) (Ing. Eng uzun ortib borayotgan quyi ketma-ketlik, LIS ) qatori x, uzunligi n Bu ketma- x[i1]<x[i2]< <x[ik] qator belgilar⋯ x shu kabi i1<i2< <ik,1 ij n , va ⋯ ⩽ ⩽ k - mumkin bo'lgan eng katta qiymat. ..................... 16 Algoritmik murakkabligi O (N 2 ). .......................................................................... 16 O(N log N) dagi yechim .......................................................................................... 17 O(N log N) dagi boshqa yechim .............................................................................. 19 Maksimal umumiy ketma-ketlikni topish ................................................................. 21 Joy uchun kurash yoki Xirshberg algoritmi. Ushbu algoritm ortidagi g'oya oddiy: agar siz x = x 1 x 2 ... x m kirish ketma-ketligini istalgan i chegara indeksida ikkita ixtiyoriy qismga bo'lsangiz, xb = x 1 x 2 ... x i va xe = x i + 1 x i + 2 ... x m , keyin y ni shunga o'xshash tarzda bo'lish usuli mavjud (y ni yb = y 1 y 2 ... y j va ye = y ga ajratadigan j indeksi mavjud. j + 1 y j + 2 ... y n ) shunday bo‘lsinki, LCS (x, y) = LCS (xb, yb) + LCS (xe, ye). Ushbu bo'linishni topish uchun y taklif qilinadi: ....................................................................................................... 26
III-bob.Xulosa ......................................................................................................... 31 Foydalanilgan adabiyotlar ...................................................................................... 33 2
I - bob . Kirish Biz quyidagi kurs ishida “ eng katta qismiy ketma- ketlikni tezkor qidirish ” mavzusi yoritildi. Eng qisqa qismiy ketma-ketlikning ikki xil turi mavjud ekanligi (quyi va yuqori) va eng qisqa qismiy ketma-ketlikni tezkor qidirish uchun Hunt- Zumanski algoritmi ,Xirshberg algoritmi kabi bir qancha algoritmlarni o’rgandek va python dasturlash tilida ifodaladek. Algoritm – ma lum bir turga oid ʼ masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Algoritmlar va ma’lumotlar strukturasi fanida eng katta qismiy ketma- ketlikni tezkor qidirish mavzusida so’z olib borishdan oldin qidirish nima ekanligini bilim olishimiz kerak. Qidirish nima ekanligini va eng soda qidirish algoritmi qanday ishlashini o’rganamiz. qidirish algoritmlarining eng soddasi bo’lgan chiziqli qidirish algoritmi haqida gaplashmoqchimiz. Bu algoritm chiziqli ma’lumotlar tuzilmalaridan (masalan, array) biror bir shart yoki qiymat bo’yicha element qidirishga mo’ljallangan va uning algoritmik murakkabligi quyidagicha: Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida element array bo’lmagan holat qaraladi va bunda algoritm maksimum n ta qadam ish bajarishi kerak bo’ladi. Eng katta qismiy ketma ketlikni tezkor qidirish mavzusi buyicha menga berilgan mavzuni yoritib chiqdim bu mavzuda qidirish algaritimining Qisman chegarasi ba'zi ketma-ketlikda emas chegarasi u mavjud bo'lsa, uning pastki biri. Raqamli ketma-ketliklarni yig'ish uchun qisman chegara ikkinchisining o'ziga xosligi tufayli odatiy chegaraga to'g'ri keladi; ammo, eng umumiy holatda, ixtiyoriy ketma-ketlik noldan cheksizgacha turli xil qisman chegaralarga ega bo'lishi mumkin. Bundan tashqari, agar odatiy chegara ketma-ketlik elementlarining soni ortib borishi bilan 3
II-bob. Asosiy qism ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH Ixtiyoriy p { 1 , 2 , ... , n) to’plam berilgan, unda eng uzun ortib borayotgan keyingi ketma – ketlikni oppish talab qilinadi . Bu Algoritmik murakkablik jihatdan O ( n log log k ) , bu yerda k eng uzun ortib boruvchi pastki ketma-ketlik deb ataladi. 1-rasm.( eng uzun ortib boruvchi pastki ketma-ketlik) O(n ) log n Algoritmi Eng katta ortib borayotgan ketma-ketlikning kattaligini topish. Bizga {a 1 ,a 2 , …,a n } ketma ketlik berilga bo’lsin. Biz elementlarni ketma-ket tartibda qayta ishlaymiz. a 1 ,a 2 ,…,a n : Har bir uzunlik uchun l = 1 , 2 , ... , n taxmin qilingan eng katta ortib borayotgn ketma-ketlikning kattaligini dan biz uzunlikning ortib borayotgan qatorida oxirgi bo'lishi mumkin bo'lgan eng kichik elementni topamiz. l uzunlikdagi B l massivga yozing . Biz uni l uzunlik uchun eng yaxshi element deb ataymiz... Agar a i har bir elementdan ko'proq B keyingi ketma-ketlik uchun hisoblangan . a 1 ,a 2 ,…,a n lardan maksimal uzunlikning ortib borayotgan pastki qatorini 4
qilishingiz mumkin, unda u oxirgi element bo'ladi. Shunday qilib, biz B massivning oxirigacha yozamiz... Aks holda a i mavjud uzunlik uchun eng yaxshi element bo'ladi va faqat bitta elementni yaxshilashi mumkin B massivdan keyin eng kichigini topamiz k : B k > a i va k : B k > a i , B k va a i elementlarni almashtiring Shuni ta'kidlash kerakki, hosil bo'lgan massiv ham biz amallarni bajarishimiz kerak bo'lgan ortib boruvchi ketma-ketlikni hosil qiladinadi. insert , next , delete ya’ni element qo’shish o’chirish kabi amallarga ko'ra, Van Emde Boas daraxti orqali amalga oshirilgan ustuvor navbatdan foydalanish tavsiya etiladi . Ushbu ma'lumotlar strukturasi tasvirlangan operatsiyalarni bajarganligi sababli O ( logk ) , bu erda k - daraxt saqlashi mumkin bo'lgan raqamlar bitlari soni, natijada olingan algoritmning murakkabligi O ( n loglog n ) ga teng bo’ladi , chunki ketma- ketlikning barcha elementlari ko'pi bilan n ga teng.Misol: Operatsiya turlari: Oldingi barcha elementlardan kattaroq elementni qo'shish: 2-rasm.( Oldingi barcha elementlardan kattaroq elementni qo'shish) Elementni ko'proq mos keladigan bilan almashtirish, ya'ni. maksimal bo'lmagan elementni qo'shish: 5