Алгоритмы с O (sqrt (N)) SPACE сложностью?

13

Существуют ли известные алгоритмы для сформулированных задач, которые требуют SPACE-сложности O (sqrt (N))? Я знаю, что существуют алгоритмы с такой большой временной сложностью.

vawd_gandi
источник
Для важной проблемы, называемой 3sum, есть следующий компромисс. Если вы хотите времени, самая известная пространственная сложность O ( √)О(N2). Смarxiv.org/abs/1605.07285О(N)
EiG

Ответы:

15

пространство несколько необычно; наиболее вероятная причина возникновения такой сложности - результат так называемойвстречи в среднейсхеме.N

Два примечательных примера на моей голове - это классическое сито Эратосфена и алгоритм гигантского шага по детскому шагу для дискретного логарифма над конечной группой.

быстрая сортировка
источник