SQRT-декомпозиция — алгоритмический подход. Он может быть применён ко многим алгоритмам, чтобы снизить их сложность.
SQRT-декомпозиция может применяться по-разному в разных случаях.
Если вам нужно много раз применять определённый алгоритм на одних и тех же данных, не изменяя их, то вы можете построить вспомогательную структуру данных, ускоряющую применение базового алгоритма. Это потребует дополнительной памяти.
Если вам нужно один раз преобразовать данные, то вы можете работать in-place, формируя вспомогательную структуру, просто переставляя данные. Это позволит снизить сложность без дополнительного расхода памяти.
Давайте разберём первый пример: снизим сложность простого алгоритма, используя дополнительную память.
Задача: дан массив чисел и интервал индексов. Найти значение минимального элемента на этом интервале.
Базовый алгоритм очевиден: просмотреть все элементы и найти минимальный. Сложность такого алгоритма O(N).
Применим SQRT-декомпозицию.
Разобъём наш массив на куски (буду называть их батчами). Размер батча будет равен √N (корню из N), округлённому вверх. Понятно, что таких батчей у нас получится примерно √N штук.
На каждом батче один раз найдём минимум и запомним эти данные. Это нам будет стоить O(√N) памяти. Время потребуется O(N); это не очень хорошо, но эту операцию нам надо проделать только один раз.
Вспомогательная структура данных готова.
Как теперь находить минимум с её помощью?
Первым делом проверяем, не попали ли концы нашего интервала в один батч. Если это так, то мы просто вычисляем минимум на интервале. И это нам обходится в O(√N) времени, так как размер батча √N.
Если же концы попали в разные батчи, то нам нужно найти минимум на трёх множествах: - правая часть батча в который попал левый край интервала, - левая часть батча в который попал правый край интервала, - минимумы всех батчей, которые оказались между левым и правым батчем.
Давайте рассмотрим пример. Пусть наш массив состоит из девяти элементов:
2 3 1 5 3 7 9 4 2
Мы разобъём его на 3 батча и в каждом найдём минимум
2 3 1|5 3 7|9 4 2
1 |3 |2
Пусть, надо найти миниму на интервале от второго до восьмого элемента:
2(3 1|5 3 7|9 4)2
1 |3 |2
Согласно нашему алгоритму, мы будем искать его на трёх множествах:
2(3 1)5 3 7(9 4)2
1 (3) |2
Таким образом, мы использовали обычный алгоритм поиска минимума, но снизили его сложность с O(N) до O(√N) с перерасходом памяти O(√N).
Реализация алгоритма на языке Python может выглядеть так:
#!/usr/bin/python2
# coding: U8
import math
import itertools
class SqrtDecompositor(object):
def __init__(self, source):
assert len(source) > 0
self.batch_size = int(math.ceil(math.sqrt(len(source))))
self.batch_mins = tuple(
map(lambda x: min(source[x : x + self.batch_size]),
range(0, len(source), self.batch_size))
)
self.source = source[:]
def min(self, a, b):
assert a < b
batch_a = a // self.batch_size + 1
batch_b = b // self.batch_size
if batch_a > batch_b:
# a и b попали в один batch
return min(self.source[a : b])
return min(itertools.chain(
self.source[a : batch_a * self.batch_size],
self.batch_mins[batch_a : batch_b],
self.source[batch_b * self.batch_size : b],
))
def main():
print SqrtDecompositor((2, 3, 1, 5, 3, 7, 9, 4, 2)).min(1, 8)
main()
На массивах порядка ста элементов, этот код работает раза в два медленней, чем обычный min(), но уже на массивах порядка 10 тысяч элементов мы получаем выигрыш на порядки. Чем больше массив, там значительней получается выигрыш, так как мы поменяли асимптотику алгоритма.
Бывают случаи, когда алгоритм должен поменять данные. Например, восстановить отсортированность последовательности.
Тогда вы можете не использовать дополнительную память, а переставлять элементы in-place.
Ключевой идеей SQRT-декомпозиции является только то, что мы разбиваем данные на √N частей, каждая из которых имеет длинну √N.