Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika yo

Algoritm samaradorligini baholash
Algoritmni amalga oshirish uchun barcha so'rovlarga javob berish uchun O (N) xotira (jami xotira 6N sarflanadi), O (N) oldindan hisoblash va O (M * log (N)) vaqtini talab qiladi.
Algoritm oldindan belgilangan daraxt bo'yicha so'rovlarga javob berishga va har biriga O(log(N)) ga kelgan zahoti javob berishga imkon beradi.
LCA qidiruv muammosini hal qilish uchun boshqa algoritmlarning samaradorligi
Ushbu muammoni hal qilish uchun bir nechta algoritmlar mavjud bo'lib, ularning har biri yozishning murakkabligi, dastlabki hisoblash vaqti, so'rovga javob berish va kerakli xotira hajmi bilan farqlanadi.
1) O(log N) da so’rov javobi, O(N) da oldindan hisoblash. Amalga oshirishning murakkabligi - "segment daraxti" yoki "sqrt-parchalanish" ma'lumotlar tuzilmasidan foydalanish zarurati.
2) Ikkilik ko'tarish usuli. Soʻrov javobi O(log N), taxmin O(log N), foydalanilgan xotira (N * log(N)). Men bergan algoritmga qaraganda bir oz yaxshiroq ishlash muddati bilan juda oddiy dastur, lekin qo'shimcha xotiradan foydalanilgan.
3) Farah-Kolton va Bender algoritmi. Bu eng optimal algoritm bo'lib, so'rovga O (1) da javob berishga imkon beradi, lekin ayni paytda juda ko'p qo'shimcha xotira talab qiladi va amalga oshirish qiyin.
Shuningdek, O (1) da so'rovga javob berishga imkon beruvchi algoritm, lekin buning uchun siz barcha so'rovlar haqida ma'lumotni oldindan bilishingiz kerak.


LCA va statik RMQ o'rtasidagi munosabat.
Masalalarning katta sinfi uchun quyidagi yordamchi masalani yechish talab etiladi. Vazifa. Ildizli daraxt beriladi. U_iui va v_ivi cho'qqilarining eng kichik umumiy ajdodini, ya'ni ildizdan u_iui gacha bo'lgan yo'lda, ildizdan v_ivi gacha bo'lgan yo'lda joylashgan ww cho'qqisini topish uchun so'rovlarga javob berish talab etiladi. vaqt shu kabilarning eng chuquri (eng pasti).
Ingliz tilida bu muammo eng kam umumiy ajdod - eng kam umumiy ajdod deb ataladi.

Vertex i - k va n uchlari uchun LCA
Yaxshiroq tushunish uchun - asta-sekin (chiziqli vaqt ichida) eng kichik umumiy ajdodni quyidagicha qidirish mumkin:
bool ancestor(int u, int v) {
return tin[u] <= tin[v] && tin[v] < tout[u]; }
int lca(int u, int v) {while (!ancestor(u, v))
u = p[u];
return u; }
Uni hal qilishning turli xil usullari mavjud va keyinroq asosiylarini ko'rib chiqamiz. Xususan, ushbu maqolada biz uni segmentdagi minimalni topish muammosiga qisqartiramiz (va aksincha).