logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH

ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

921.0625 KB
Ko'chirib olish
“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 ⟶    3-rasm.( maksimal bo'lmagan elementni qo'shish): Ketma-ketlik misoli 4-rasm. Har bir qo'shimcha bilan navbat holati 5-rasm. 6 Endi shu amallarni python dasturlash tilida ifodalaymiz. int LIS(ππ[n]) PriorityQueue B // Ustuvor navbat int k = 0 // eng ortib boruvchi pastki ketma-ketlik uzunligi for i = 1 to n x = ππ[i] // har qanday holatda navbatga yangi element qo’shing //eski elementlarni esa o’chiring B.insert(x) if ∃∃ B.next(x) // element qo’shish — maksimal bo’lmagan // x dan keying elementni o’chiring B.delete(B.next(x)) else // element qo’shish — maksimal // qiymat oshdi k = k + 1 return k Qisman ketma-ketlik chegarasi . 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- 7 ketlik elementlarining soni ortib borishi bilan yaqinlashadigan nuqtani tavsiflasa, qisman chegaralar ketma-ketlikning cheksiz ko'p elementlari mavjud bo'lgan nuqtalarni tavsiflaydi. Qisman chegaraning ikkita muhim maxsus holati yuqori va pastki chegaralardir. Eng katta qismiy ketma- ketlikni tezkor qidirish uchun algoritm . Biz juftlarni yodlaymiz: har bir element uchun biz uning "oldingi" ni yozamiz. Keyin, navbatdagi oxirgi elementdan boshlab, B oldingilarni kesib o'tish , biz eng katta qismiy ketma-ketlini tiklashimiz mumkin. 6-rasm. Dasturlash tilida esa int[] LIS(π[n]) PriorityQueue B int k = 0 int predecessor[n] // qo’shimcha n massiv for i = 1 to n 8 x = π[i] B.insert(x) predecessor[x] = B.prev(x) if ∃ B.next(x) B.delete(B.next(x)) else k = k + 1 int result[k] int cur = B.max for i = k - 1 downto 0 result[i] = cur cur = predecessor[cur] return result quyidagicha ifodalanadi. O (n log log k) optimallashtirish. van Emde Boas daraxt uchun operatsiyalarini amalga   O ( loglog k ) murakkablikda , qayta ishlangan qiymatlarning alifbosini qisqartirish kerak O ( k ) … Faraz qilaylik, biz raqamning bunday yaqinligini bilamiz k raqam m : m ⩾ k . Buni qanday topish mumkinligini keyinroq muhokama qilamiz. Element kalitlarini qayta ishlash jarayonida yuqoridagi algoritm LIS faqat navbat bilan ishlaydi B va navbatda bo'lmagan ketma-ketlikning oldingi elementlariga bog'liq emas. Shuning uchun, agar biz butun ketma-ketlikni bloklarga ajratsak m elementlar (oxirgi blok kamroq bo'lishi mumkin) va biz har birini almashtirish sifatida ishlata olamiz, navbatni saqlash avvalroq hisoblangan bloklar uchun asimptotik vaqtni 9 olamiz O ( n loglog ( k + m )) v a beri m ⩾ k m ⩾ k , keyin O ( n loglog m ) .. (Biz bloklarni ketma-ket qayta ishlaymiz, ya'ni bizda bo'lishi mumkin bo'lgan oldingi blokdan k to'ldirilgan navbatdagi qiymatlar m keyingi blokning qiymatlari - biz yuqori chegarani olamiz k + m qayta ishlash mumkin bo'lgan qiymatlar.) Bloklarga bo'linish Ketma ketlik S bloklargabo'lingan Cj , j = 1 , …, ⌈ nm ⌉ Cj, j=1, …, ⌈ nm ⌉ : Cj =( π ( j − 1 ) m + 1 , π ( j − 1 ) m + 2 , … , π ( j − 1 ) m + m )) bilan belgilaymiz Csj tartiblangan blok C j ... Biz tartiblangan va tartiblanmagan bloklarni xotirada saqlaymiz. Har bir blokni alohida raqamli saralash bizga ish vaqtini beradi. Keling, har bir elementni qo'shamiz p joylashgan blok raqami va ushbu blokda ofset. Endi blok raqamini eng muhim bit, elementni esa eng kam ahamiyatli bit sifatida hisobga olsak (biz blok ichidagi ofset bo‘yicha saralay olmaymiz), siz chiziqli vaqtda raqamli saralash bo‘yicha saralashingiz mumkin. O ( n ) O(n) , chunki elementlarning qiymatlari va blok raqamlari n dan oshmaydi ... Saralangan blokda hosil bo'lgan siljishlar almashinuvi almashtirishning teskari almashinuvidan boshqa narsa emas. p p , uning elementlari asl blokning elementlari sifatida bir-biri bilan bog'liq. Bular. element bo'lsa p p blokdagi asl almashtirishda Cj holatda i i , keyin blokda Cjs u holatda ... Endi esa m=5 holatda quyidagilarga ega bo’lamiz: Teskari almashtirish natijasida esa quyidagilarga ega bo’lamiz. 7-rasm. Blokni qayta ishlash. Blokni qayta ishlashda har bir element x bu blok ichida biz kalitni birma-bir moslashtiramiz y = key ( x );   x = elt ( y ) ) ularning 10 qiymatlari intervalda bo'lishi uchun { 1 , 2 , ... , 2 m } Navbat B to'g'ridan-to'g'ri element kalitlari bilan ishlaydi. Blok bilan ishlash Cj , biz kalitlari navbatda turgan elementlarni birlashtiramiz B , Bilan Cjs ro'yxatga birlashtiramiz . Biz buni taxmin qilganimizdan m ⩾ k , keyin kalitlar soni B dan m ko’p emas, keyin uzunlik birlashtirish Ko'p emas 2 m , bu to'plamdagi kalitlarni aniqlash imkonini beradi { 1 , 2 , ... , 2 m } ... Yuqorida aytib o'tilganidek, kalitlari B bo'lgan elementlar, Tartibini narvondan ajratish, shuning uchun Birlashtirish ishlashini algoritmik murakkabligi O(m) . ga teng . Natijada biz tartiblangan ro'yxatni olamiz va birlashtiramiz ... Keling, har bir elementga kalitni ushbu ro'yxatdagi o'rni sifatida moslashtiramiz, keyin bu gaplar to'g'ri bo'ladi. . elt ( x )= merged [ x ] elt(x)=merged[x] и ( π i < π k ⟺ key ( π i )< key ( π k )) qayerda pi , pk ∈ me r g e shuning uchun element tugmachalarining har qanday ortib boruvchi ketma-ketligi elementlarning ortib borayotgan ketma-ketligiga mos keladi. Shunday qilib, ustuvor navbat elementlarning kalitlari bilan to'g'ri ishlashi mumkin bo'ladi. Blok elementlariga mos keladigan tugmalar ketma-ketligini toping Csj ... Bu ketma-ketlikni almashtirish orqali harakat qilish pj , biz asl blokning tartibida kalitlar ketma-ketligini olamiz. Qolgan kiritilgan kalitlar birlashtiladi , lekin ishlov berilayotgan blokdagi elementlarning kalitlari emas, ular navbatdagi elementlarning kalitlari bo‘ladi. B ... Navbat yangilanmoqda bu kalitlar bilan. Keyin biz algoritmni ishga tushiramiz L I S , element kalitlari uchun Cj asl ketma- ketlik tartibida. Natijada bloklarni qayta ishlash quyidagi bosqichlarga bo'linadi:  Biz navbatdan chiqamiz B B kalitlari x x , ularni elementlarga aylantiring ..  Elementlarni birlashtirish keyingi tartiblangan blok bilan Cjs ro'yxatga birlashtiriladi, ikkita kichik massivni yaratish orqali men va men nd bitta ind bitta ro'yxat elementlarining indekslarini saqlash va mos ravishda ro'yxatda birlashtiriladi. 11  Ro'yxatdagi tugmalar ketma-ketligi bo'yicha harakat qilish men qayta tartibga solish pj biz kalitlarni asl ketma-ketlik tartibida olamiz.  ichiga kiriting B ro'yxat elementlarining yangi kalitlari (elementlar men nd bitta ind bitta ).  Blok elementlarining kalitlarini algoritm yordamida dastlabki ketma-ketlik tartibida qayta ishlaymiz L I S ... eng katta qismiy ketma-ketlikni tiklash uchun biz shuningdek, kalitlarga mos keladigan elementlar bilan ishlaydigan "oldingi" qatordan foydalanamiz. e l t ( x ) elt(x) ... Birinchi blok Navbatdan beri B boshida bo'sh, keyin me r g e d =Cs Ro'yxatdagi elementlarga kalitlarni belgilash birlashtirish ushbu ro'yxatdagi indekslari sifatida. Biz elementlarning kalitlari ketma-ketligini asl ketma-ketlik tartibida tiklaymiz, ofsetlarni almashtirish orqali harakat qilamiz. pbittapbitta tartiblangan blokdagi tugmalar ketma-ketligi bilan. 8-rasm.(  Algoritm  yordamida  blokni  qayta  ishlash   L   I   S .) Natijada, biz olamiz B : { 1 , 2 , 3 } me r g e d :{3,4,8,9,10} Ikkinchi blok Elementlarni qayta tiklash B : { 1 , 2 , 3 } dan me r g e d :{3,4,8,9,10} : { 3 , 4 , 8 } . 12 Birlashtirish C2s va qaytarib olingan narsalar B v birlashtirish va olingan ro'yxatdagi elementlarning indekslari sifatida elementlarga kalitlarni tayinlang: 9-rasm. Elementlarning kalitlarini oling Cs 2 va almashtirish orqali harakat qiluvchi dastlabki ketma-ketlik tartibida p 2 kalitlarning almashinishini toping : Navbatdagi kalitlarni yangilaymiz: 10-rasm. ishga tushirish L I S LIS blok uchun: 11-rasm. Natijada biz quyidagilarni olamiz: B : { 1 , 2 , 5 , 8 } me r g e d :{1,2,3,4,5,6,8,12} Uchinchi blok 13 Elementlarni qayta tiklash B : { 1 , 2 , 5 , 8 } dan me r g e d : {1,2,3,4,5,6,8,12} : { 1 , 2 , 5 , 12} Birlashtirish Cs3 va qaytarib olingan narsalar B va elementlarga kalitlarni tayinlang: 18-rasm. Elementlarning kalitlarini oling C3s va almashtirish orqali harakat qiluvchi dastlabki ketma-ketlik tartibida kalitlarning almashinishini toping p3 : Eski kalitlarni yangilash: 12-rasm. shga tushirish L I S LIS blok uchun: 13-rasm. Algoritmni bajarish natijasi: B : { 1 , 2 , 3 , 4 , 5 } me r g e d :{1,2,5,7,11,12} 14 Biz eng katta qismiy ketma-ketlik uzunligini olamiz - 55 . Eng uzun ortib borayotgan qismiy ketma-ketmaketlikni qayta tiklash 14-rasm. dan tiklanishni boshlaymiz me r g e d [ 5 ]= 11 Blok hajmini topish Ketma-ketlikni ko'rib { m 0 , m 1 , m 2 , …} - ba'zilari kamroq mi + 1 = m log mi = 2 log mi+1=mi log mi=2log 2 qiymatga ega k k ... Ushbu ketma-ketlikning elementlari uchun yuqorida keltirilgan algoritmni ketma- ket bajaramiz. Agar navbat o'lchami bo'lsa B kattalashib bormoqda mi , keyin shart m ⩾ k bajarishni to'xtatadi, keyin biz algoritmni to'xtatamiz va keyingi qiymatga o'tamiz mi + 1 . Hamma uchun mi mi ro'yxat hajmi me r g e d . Ko'p emas 2 mi , va jami bloklar soni ⌈ n / mi ⌉ ga teng bo’ladi. Keyin ketma-ketlik elementlariga yangi kalitlarni tayinlashning umumiy soni, shuningdek ro'yxatlardagi birlashma operatsiyalari soni ko'p emas 2 cm i ⋅ nm i = O ( n ) . bu yerda c qandaydir doimiydir. Har bir ustuvor navbat operatsiyasi talab qiladi O ( loglog m i ) vaqt, chunki elementlar B Ko'p emas 2mi elementga ega. Barcha qayta ishlangan qiymatlar uchun algoritmning umumiy ishlash vaqti   ..   e'tibor bering, chunki boshqacha   mi < klogk mi<klog k   , bu haqiqatga zid keladi   mi   - kattaroq bo'lganlarning birinchisi   k ..   Binobarin,   . Biz algoritmning vaqtga nisbatan murakkabligini O ( n loglog k )   ekanligini topamiz . 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 [ i 1 ]< x [ i 2 ]< ⋯ < x [ i k ] qator belgilar x shu kabi i 1 < i 2 < ⋯ < i k , 1 ⩽ i j ⩽ n , va k - mumkin bo'lgan eng katta qiymat. Algoritmik murakkabligi O (N 2 ). Keling, d massiv tuzamiz , qayerda d[i] Indeksli elementda tugaydigan eng uzun o suvchi quyi ketma-ketlikning uzunligiʻ i ga teng. Biz massivni asta-sekin to'ldiramiz – birinchi d[ 0 ], keyin d[ 1 ] va hokazo. Bizning muammomizga javob massivning barcha elementlarining maksimali bo'ladi d ... Massivni to'ldirish quyidagicha bo'ladi: agar d d [ i ]= 1 , keyin qidirilayotgan ketma-ketlik faqat sondan iborat a [ i ] > 1 , keyin raqamdan oldin a [ i ] pastki qator boshqa raqamni o'z ichiga oladi. Keling, uni takrorlaymiz: u har qanday element bo'lishi mumkin a [ j ] ( j = 0 ... i - 1 )a[j](j=0 ...i-bitta) lekin shunday a [ j ] < a [ i ] . Keling, bir qadamda keyingisini hisoblashimiz kerak d[i] ... Massivning barcha elementlari d dan oldin allaqachon hisoblangan. Shunday qilib, bizning d[i] quyidagicha hisoblashimiz mumkin: d [ i ]= 1 +max j = 0 .. i − 1 d [ j ] d[i]=1+maxj=0..i−1d[j] va quyidagi shart bilan tekshirilib boriladi a [ j ]< a [ i ]. Hozircha biz eng katta ortib boruvchi pastki ketma-ketlikning faqat maksimal uzunligini topdik, ammo biz uni o'zidan chiqara olmaymiz. Javobni tiklash uchun massiv yarataylik prev [ 0... n − 1 ] qayerda   prev [ i ] bo’lsa massivdagi indeksni bildiradi a [ , bunda maksimal qiymatga erishildi d[i] ... Javobni ko'rsatish uchun biz maksimal qiymatlarga ega elementdan o'tamiz d[i] ajdodlariga ko'ra. Endi esa bu jarayonni python dasturlash tilidagi kodini yozamiz: vector<int> findLIS(vector<int> a): int n = a.size 16 int prev[0..n - 1] int d[0..n - 1] for i = 0 to n - 1 d[i] = 1 prev[i] = -1 for j = 0 to i - 1 if (a[j] < a[i] and d[j] + 1 > d[i]) d[i] = d[j] + 1 prev[i] = j pos = 0 length = d[0] for i = 0 to n - 1 if d[i] > length pos = i length = d[i] vector<int> answer while pos != -1 answer.push_back(a[pos]) pos = prev[pos] reverse(answer) return answer O(N log N) dagi yechim Ushbu muammoni tezroq hal qilish uchun biz quyidagi dinamikani tuzamiz: d [ i ] ( i = 0... n )   - uzunlikning ortib boruvchi ketma-ketligi i tugaydigan raqam, va agar 17 bunday raqamlar bir nechta bo'lsa, ularning eng kichigi. Dastlab, biz buni taxmin qilamiz d [ 0 ] = - ∞ , va boshqa barcha elementlar d [ i ] = ∞ ... Ushbu dinamikaning ikkita muhim xususiyatiga e'tibor bering : d [ i - 1 ] ⩽ d[i] , Barcha uchun i = 1 va har bir element a [ i ] ko'pi bilan bitta elementni yangilaydi d [ j ] . Bu shuni anglatadiki, keyingi ishlov berishda a [ i ] , biz uchun mumkin O ( logn ) murakkablikdagi massivda ikkilik qidiruvdan foydalanish d joriydan katta yoki unga teng bo'lgan birinchi sonni toping a [ i ] va uni yangilang. Javobni tiklash uchun biz ikkita massivni to'ldirishni qo'llab-quvvatlaymiz: p o s va prev ... p o s [ i ] biz uzunlikning optimal keyingi ketma-ketligi tugaydigan element indeksini saqlaymiz va ichida p r e v [ i ] - oldingi elementning joylashuvi a [ i ] mavjud bo’ladi. Endi bu jarayonni dasturlash tilida yozamiz. vector<int> findLIS(vector<int> a): int n = a.size int d[0..n] int pos[0..n] int prev[0..n - 1] length = 0 pos[0] = -1 d[0] = for i = 1 to n d[i] = for i = 0 to n - 1 j = binary_search(d, a[i]) 18 if (d[j - 1] < a[i] and a[i] < d[j]) d[j] = a[i] pos[j] = i prev[i] = pos[j - 1] length = max(length, j) vector<int> answer p = pos[length] while p != -1 answer.push_back(a[p]) p = prev[p] reverse(answer) return answer O(N log N) dagi boshqa yechim Yana bir yechim bor, bu bizga eng uzun ortib boruvchi ketma-ketlikning uzunligini topishga imkon beradi, lekin bu pastki ketma-ketlikni tiklash imkoniyatisiz. Buning uchun biz Young stolidan foydalanamiz. U shunday xususiyatga egaki, tablaning birinchi qatorining uzunligi kerakli qiymat bo'ladi [1] . Tabloning o'zi joylashuvni ko'rsatadi   n 1 + n 2 +...+ n M chapga tekislangan satrlar massividagi alohida butun sonlar, bu yerda i i qatorni o'z ichiga 19 oladi ni ni elementlar; lekin har bir satrda elementlar chapdan o ngga, har bir ʻ ustundagi elementlar esa yuqoridan pastga qarab ortadi. Tabloni yaratish uchun siz keyingi elementni o'qishingiz kerak ai ai dan katta yoki teng bo'lsa nj nj , qayerda j - satrning uzunligi, keyin faqat satrning oxiriga qo'shing, agar kamroq bo'lsa, birinchi elementni topishingiz kerak. b b bu berilganidan kattaroqdir ai ai ... Elementni qo'ying a ning o'rniga b ... Element b bilan bir xil harakatlarni bajarish talab etiladi a ga ham , faqat allaqachon yoqilgan i + 1 tabla chizig'i. Massivda tabla qurishga misol a = [ 3 , 4 , 9 , 2 , 5 , 1 ] 1. 3- Elementni oling . Biz buni ko'ramiz 3 >0 indeksli katakning birinchi qatorida joylashgan j = 0 ... Biz ko'paytiramiz j va t [ i ] [ j ] = 3 ... 3 2. 4-Elementni oling . Biz buni ko'ramiz 4 >3 ... Biz ko'paytiramiz j va t [ i ] [ j ] = 4 ... 3 4 3. Xuddi shunday element uchun 9 ... 3 4 9 4. 2 Elementni oling . Chunki 2 <9 , keyin ikkilik qidiruv orqali biz kerakli pozitsiyani topamiz z shu kabi t [ i ] [ z - 1 ] ⩽ 2 < t [ i ] [ z ] . Bunday holda, bu birinchi pozitsiya. Biz tayinlaymiz t [ i ] [ z ] = 2 va xuddi shu amalni bajaring, lekin indeksli chiziq uchun i + 1 ga oshiring … 2 4 9 3 5. Element uchun ham xuddi shunday 5 uchun ham. 20 2 4 5 3 9 6. Xuddi shunday element 1 uchun ... 1 4 5 2 9 3 Shunday qilib, massiv uchun eng uzun o'suvchi pastki ketma-ketlikning uzunligi a 3 ga teng (masalan, elementlarning pastki ketma-ketligi [ 3 , 4 , 9 ] [3,4,9] ). Maksimal umumiy ketma-ketlikni topish Ketma-ket narsalarning tartiblangan to'plamidir. Satr ketma-ketlikning maxsus holatidir, keyingi misollar oddiylik uchun faqat satrlarni ko'rib chiqadi, ammo o'zgartirishlarsiz ular ixtiyoriy matn yoki boshqa ketma-ketlik uchun ishlatilishi mumkin. Bir natija bor bo'lsin x elementlardan tashkil topgan x 1 x 2 ... x m va a oqibat y elementlar iborat y 1 , y 2 ... y n . z - x ning kichik ketma- ketligi, agar x elementlarning qat'iy ortib borayotgan indekslari to'plami mavjud bo'lsa.undan z olinadi . Umumiy tadrijiylik uchun x va y bir natija z bir tadrijiylik ham x va tadrijiy y . Maksimal umumiy pastki ketma-ketlik maksimal uzunlikdagi umumiy ketma- ketlikdir. Keyinchalik matnda biz LCS qisqartmasidan foydalanamiz . Misol tariqasida, x = HA B R AHA BR , y = HARB OU R , bu holda LCS (x, y) = HARBR bo'lsin. ... Siz to'g'ridan-to'g'ri LCS ni hisoblash algoritmiga o'tishingiz mumkin, ammo bu bizga nima uchun kerakligini tushunish yaxshi bo'lar edi. 21 Amalda qo'llash Eng keng tarqalgan foydalanish GNU diff kabi fayllarni taqqoslash dasturlarida. Ikkita matn uchun LCS ni topib, x ni y ga yoki aksincha aylantirish uchun elementar o'zgarishlar ro'yxatini tuzish juda oddiy vazifadir. Bonus sifatida, umumiy pastki ketma-ketlikning uzunligiga asoslanib, siz ikkita ketma-ketlikning o'xshashligini aniqlash uchun metrikani belgilashingiz mumkin. Hamma narsa, endi siz aniq biznesga kirishingiz mumkin. Birinchi  yondashuv  yoki  xalq  san'ati Birinchidan, bir nechta kuzatishlar: 1. Agar x va y ketma-ketliklar uchun biz allaqachon LCS (x, y) = z ni hisoblagan bo'lsak, u holda bir xil elementni qo'shish orqali x va y dan olingan ketma-ketliklar uchun LCS z va ushbu qo'shilgan elementdan iborat bo'ladi. 2. Agar x va y ketma-ketliklariga bir xil element qo‘shsak, shu tarzda olingan xa va yb uchun LCS ikkitadan kattaroq bo‘lishi kerak: LCS (x, yb) yoki LCS (xa, y) Ushbu kuzatishlar rekursiyani amalga oshirish uchun allaqachon yetarli.(python dasturlash tilida) def LCS_RECURSIVE(x, y): if len(x) == 0 or len(y) == 0: return [] if x[-1] == y[-1]: 22 return LCS_RECURSIVE(x[:-1], y[:-1]) + [x[-1]] else: left = LCS_RECURSIVE(x[:-1], y) right = LCS_RECURSIVE(x, y[:-1]) return left if len(left) > len(right) else right Endi siz ushbu dasturda nima noto'g'ri ekanligini o'ylashingiz mumkin. Eng yomon holatda, agar x va y o'rtasida bir xil elementlar bo'lmasa, LCS_RECURSIVE len (x) + len (y) rekursiya darajasida 2 len (x) + len (y) marta chaqiriladi . Ishlash uchun ko'zimizni yumsak ham, kod: from uuid import uuid4 x = [uuid4().hex for _ in xrange(500)] y = [uuid4().hex for _ in xrange(500)] print LCS_RECURSIVE(x,y) sys.setrecursionlimit ga qo'shimcha qo'ng'iroq qilmasdan, u muvaffaqiyatsiz bo'ladi. Eng muvaffaqiyatli amalga oshirish emas. Dinamik dasturlash yoki 64 kb hamma uchun etarli. Ko'rib chiqilgan algoritm Needleman-Wunsch algoritmi sifatida ham tanilgan. Butun yondashuv matritsani bosqichma-bosqich to'ldirishga to'g'ri keladi, bu erda satrlar x element, ustunlar esa y elementdir. To'ldirishda allaqachon o'tkazilgan kuzatishlardan kelib chiqadigan ikkita qoida mavjud: 1. Agar x i elementi y j ga teng bo'lsa , u holda (i, j) katakchada (i-1, j-1) katakchaning qiymati yoziladi. bitta qo'shilishi 2. Agar x i elementi y j ga teng bo'lmasa , u holda (i, j) katakchaga (i-1, j) va (i, j-1) qiymatlarning maksimali yoziladi. . To'ldirish i va j bo'ylab er-xotin aylanada sodir bo'ladi, shuning uchun har bir 23 iteratsiyada ushbu bosqichda talab qilinadigan hujayra qiymatlari allaqachon hisoblab chiqilgan: def fill_dyn_matrix(x, y): L = [[0]*(len(y)+1) for _ in xrange(len(x)+1)] for x_i,x_elem in enumerate(x): for y_i,y_elem in enumerate(y): if x_elem == y_elem: L[x_i][y_i] = L[x_i-1][y_i-1] + 1 else: L[x_i][y_i] = max((L[x_i][y_i-1],L[x_i-1][y_i])) return L 15-rasm. 24 Qiymat to'g'ridan-to'g'ri oshirilgan hujayralar ta'kidlangan. Matritsani to'ldirgandan so'ng, ushbu hujayralarni ulab, biz kerakli LCSni olamiz. Bunday holda, siz maksimal indekslardan minimal darajaga o'tish orqali ulanishingiz kerak, agar hujayra ajratilgan bo'lsa, biz LCS ga mos keladigan elementni qo'shamiz, agar bo'lmasa, qayerga qarab yuqoriga yoki chapga siljiymiz. kattaroq qiymat matritsada: def LCS_DYN(x, y): L = fill_dyn_matrix(x, y) LCS = [] x_i,y_i = len(x)-1,len(y)-1 while x_i >= 0 and y_i >= 0: if x[x_i] == y[y_i]: LCS.append(x[x_i]) x_i, y_i = x_i-1, y_i-1 elif L[x_i-1][y_i] > L[x_i][y_i-1]: x_i -= 1 else: y_i -= 1 LCS.reverse() return LCS Allogoritimning murakkabligi O (len (x) * len (y)), xotiradan bir xil ball. Shunday qilib, agar men 100 000 satrdan iborat ikkita fayl o'rtasida satrma-satr 25 solishtirmoqchi bo'lsam, xotirada 10 10 elementdan iborat matritsani saqlashim kerak bo'ladi . Bular. real foydalanish MemoryError-ni deyarli ko'kdan chiqarish bilan tahdid qiladi. Keyingi algoritmga o'tishdan oldin, shuni yodda tutingki, L matritsasini x elementlari ustidagi har bir iteratsiyada to'ldirganda, bizga faqat oldingi harakat paytida olingan qator kerak bo'ladi. Bular. agar muammo LCS ning o'zini hisoblamasdan faqat LCS uzunligini topish bilan cheklangan bo'lsa, u holda L matritsasining faqat ikkita qatorini saqlab, xotiradan foydalanishni O (len (y)) ga kamaytirish mumkin edi. bir vaqt. 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: 1. L dinamik matritsasini xs va y uchun fill_dyn_matrix bilan to'ldiring. L1 hisoblangan L matritsaning oxirgi qatorini tenglashtiramiz 2. * xe va * y uchun L matritsasini to'ldiring (xe va y uchun teskari ketma- ketliklar, Python shartlarida: ro'yxat (teskari (x)), ro'yxat (teskari (y))). Hisoblangan L matritsaning oxirgi qatoriga * L2 tenglang, L2 daryo * L2 3. L1 [j] + L2 [j] yig'indisi maksimal bo'lgan indeksga teng j ni oling Bu L matritsasini ikkita qarama-qarshi tomondan to'ldirish sifatida ifodalanishi mumkin: 26 16-rasm.( L matritsas) E'tibor bering, L matritsasining faqat oxirgi qatoriga ehtiyoj borligi sababli, hisoblash paytida butun matritsani saqlash shart emas. Fill_dyn_matrix ilovasini biroz o'zgartirib, biz quyidagilarni olamiz: def lcs_length(x, y): curr = [0]*(1 + len(y)) for x_elem in x: prev = curr[:] 27 for y_i, y_elem in enumerate(y): if x_elem == y_elem: curr[y_i + 1] = prev[y_i] + 1 else: curr[y_i + 1] = max(curr[y_i], prev[y_i + 1]) return curr Endi to'g'ridan-to'g'ri, algoritmning o'zi haqida. Bu klassik bo'linish va zabt etish: x ketma-ketligida elementlar mavjud ekan, biz x ni ikkiga bo'lamiz, y uchun mos bo'lim topamiz va ketma-ketlik juftliklari (xb, yb) va (xe,) uchun rekursiv chaqiruvlar yig'indisini qaytaramiz. ye). E'tibor bering, arzimas holatda, agar x bitta element bo'lsa va y da sodir bo'lsa, biz shunchaki bitta x elementdan ketma- ketlikni qaytaramiz. def LCS_HIRSHBERG(x, y): x_len = len(x) if x_len == 0: return [] elif x_len == 1: if x[0] in y: return [x[0]] else: return [] 28 else: i = x_len // 2 xb, xe = x[:i], x[i:] L1 = lcs_length(xb, y) L2 = reversed(lcs_length(xe[::-1], y[::-1])) SUM = (l1 + l2 for l1,l2 in itertools.izip(L1, L2)) _, j = max((sum_val, sum_i) for sum_i, sum_val in enumerate(SUM)) yb, ye = y[:j], y[j:] return LCS_HIRSHBERG(xb, yb) + LCS_HIRSHBERG(xe, ye) Endi bizning xotira talablarimiz O (len (y)), hisoblash uchun zarur bo'lgan vaqt ikki baravar ko'paydi, ammo asimptotik ravishda hali ham O (len (x) len (y)). Hunt-Zumanski algoritmi Bizga kerak bo'lgan birinchi narsa - ikkinchi ketma-ketliklar elementlarining indekslarini o'z ichiga olgan xesh-jadval, matchlar ro'yxatini yaratish. Buning uchun talab qilinadigan vaqt O (len (y)). Quyidagi python kodi buni amalga oshiradi: y_matchlist = {} for index, elem in enumerate(y): indexes = y_matchlist.setdefault(elem, []) indexes.append(index) y_matchlist[elem] = indexes 29 "HARBOR" ketma-ketligi uchun xesh {'A': [1], 'B': [3], 'H': [0], 'O': [4], 'R': [2bo'ladi.,6],'U':[5]}. Keyin, x ketma-ketligining elementlarini takrorlab, THRESH massivini tayyorlangan moslik ro yxatidagi mos indekslar bilan to ldiring, shunda k-ʻ ʻ THRESH elementining qiymati y_index indeksi bo lishi kerak, THRESH [k-1] ʻ <y_index va y_index <THRESH [k]. Shunday qilib, istalgan vaqtda THRESH massivi saralanadi va mos k ni topish uchun ikkilik qidiruvdan foydalanishimiz mumkin. THRESH elementini yangilaganimizda, biz LCS ga y_index ga mos keladigan ketma-ketlik elementini ham qo'shamiz. Quyidagi kod aniqlik kiritishi mumkin: x_length, y_length = len(x), len(y) min_length = min(x_length, y_length) THRESH = list(itertools.repeat(y_length, min_length+1)) LINK_s1 = list(itertools.repeat(None, min_length+1)) LINK_s2 = list(itertools.repeat(None, min_length+1)) THRESH[0], t = -1, 0 for x_index,x_elem in enumerate(x): y_indexes = y_matchlist.get(x_elem, []) for y_index in reversed(y_indexes): k_start = bisect.bisect_left(THRESH, y_index, 1, t) k_end = bisect.bisect_right(THRESH, y_index, k_start, t) 30 for k in xrange(k_start, k_end+2): if THRESH[k-1] < y_index and y_index < THRESH[k]: THRESH[k] = y_index LINK_x[k] = (x_index, LINK_x[k-1]) if k > t: t = k Shundan so'ng, biz LINK_x dan ketma-ketlikni yig'ishimiz kerak. Ushbu algoritmning ishlash vaqti O ((r + n) log n), bu erda n - kattaroq ketma- ketlikning uzunligi va r - mos keladiganlar soni, eng yomon holatda r = n * n bilan, biz olamiz ish vaqti oldingi yechimga qaraganda yomonroq. Xotira talablari O(r+n)_tartibida_qoladi. Ushbu muammoni hal qiladigan juda ko'p algoritmlar mavjud, asimptotik tarzda, eng samarali algoritm (Masek va Paterson) O (n * n / log n) vaqtini taxmin qiladi III-bob.Xulosa 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.Algoritmlarning murakkabligini baholadek va ularning bir biridan afzalliklarini aniqladek va eng katta qismiy ketma- ketlikni tezkor qidirish borasida ma’lumotlarga ega bo’ldik. Bu vaqtdan unumli foydalanish va kerkli bo’lgan ma’lumotlarni oson va tez topish imkoniyatini yaratadi. Dastur kodini yozish va xatoliklardan xoli bo’lgan dastur orqali biz 31 qidirayotgan ma’lumotlarni osongina topa olamiz Endi to'g'ridan-to'g'ri, algoritmning o'zi haqida. Bu klassik bo'linish va zabt etish: x ketma-ketligida elementlar mavjud ekan, biz x ni ikkiga bo'lamiz, y uchun mos bo'lim topamiz va ketma-ketlik juftliklari va uchun rekursiv chaqiruvlar yig'indisini qaytaramiz. ye). E'tibor bering, arzimas holatda, agar x bitta element bo'lsa va y da sodir bo'lsa, biz shunchaki bitta x elementdan ketma-ketlikni qaytaramiz. Qiymat to'g'ridan- to'g'ri oshirilgan hujayralar ta'kidlangan. Matritsani to'ldirgandan so'ng, ushbu hujayralarni ulab, biz kerakli LCSni olamiz. Bunday holda, siz maksimal indekslardan minimal darajaga o'tish orqali ulanishingiz kerak, agar hujayra ajratilgan bo'lsa, biz LCS ga mos keladigan elementni qo'shamiz, agar bo'lmasa, qayerga qarab yuqoriga yoki chapga siljiymiz. 32 Foydalanilgan adabiyotlar 1. Polatov A.M. Algoritmlar va C++ tilida dasturlash asoslari. Toshkent. “Universitet” - 2017. 123 bet 2. Madraximov Sh.F., Ikramov A.M., Babajanov M.R. C++ tilida programmalash bo’yicha masalalar to’plami. O’quv qo’llanma. T., O’zbekiston Milliy universiteti, “Universitet” nashriyoti, 2014. - 160 b 3. Holmatov T.X, Toyloqov N.I Amaliy, dasturlash va kompyuterning matematika ta'minoti. T. Mexnat, 2000 y. 4. Akbaraliyev B.B., Yusupova Z.D., “Ma’lumotlar tuzilmasi va algoritimlar”, Toshkent 2013. Elektron veb-sahifa: 1. https://bit.ly/3ql1Spk 2. https://bit.ly/33WfAHF 3. https://en.wikipedia.org/wiki/Longest_increasing_subsequence 4. https://en.wikipedia.org/wiki/Robinson %E2%80%93Schensted_correspondence#Properties 5. https://ru.wikipedia.org/wiki/ %D0%A7%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD %D1%8B%D0%B9_%D0%BF %D1%80%D0%B5%D0%B4%D0%B5%D0%BB_%D0%BF%D0%BE %D1%81%D0%BB%D0%B5%D0%B4%D0%BE %D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD %D0%BE%D1%81%D1%82%D0%B8 6. https://habr.com/ru/post/142825/ 33 34

“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

O'xshashlar

Eng katta qismiy ketma-ketlikni qidirish
ISH QIDIRISH ILOVASI.
Grafikda bog’liq kompenentlarini qidirish algaritmlari
Qidiruv algoritmlari
SARALASH VA QIDIRISH UCHUN SAMARALI ALGORITMLAR