Алгоритми Мо

Алгоритми Мо

Муқаддима ба Алгоритми Мо

Алгоритми Мо техникаест, ки ба Алгоритми Декомпозитсияи Решаи Квадратӣ такя мекунад. Он барои ҷавоб додан ба масъалаҳои дархостҳои диапазонӣ самаранок аст, махсусан вақте ки дархостҳо массиви статикӣ (бе навсозӣ) дар бар мегиранд ва метавонанд офлайн коркард шаванд. Ин алгоритм махсусан барои масъалаҳое муфид аст, ки коркарди дархостҳо гарон аст.

Мафҳум

Алгоритми Мо дархостҳои диапазониро бо гурӯҳбандӣ кардани онҳо ба блокҳо ва тартиб додани блокҳо оптимизатсия мекунад, то хароҷоти гузаштан аз як диапазон ба диапазони дигар кам карда шавад. Ин равиш шумораи ҳисоббарориҳои лозим барои коркарди ҳамаи дархостҳоро ба таври назаррас коҳиш медиҳад.

Маҳдудияти Декомпозитсияи SQRT

Барои фаҳмидани он ки Алгоритми Мо чӣ корро беҳтар мекунад, бояд ба ёд орем, ки дархостҳо дар декомпозитсияи муқаррарии SQRT чӣ гуна коркард мешуданд. Инро метавон чунин ҷамъбаст кард:

• Барои ҳар як дархост $q_i = [L_i, R_i]$ мо ҳамаи блокҳоеро меёбем, ки ягон қисми -ро дар бар мегиранд. Дар беҳтарин ҳолат метавонад ҳадди аксар чунин блок бошад.