Существуют ли известные алгоритмы для сформулированных задач, которые требуют SPACE-сложности O (sqrt (N))? Я знаю, что существуют алгоритмы с такой большой временной сложностью.
complexity-theory
asymptotics
space-complexity
vawd_gandi
источник
источник
Ответы:
пространство несколько необычно; наиболее вероятная причина возникновения такой сложности - результат так называемойвстречи в среднейсхеме.N--√
Два примечательных примера на моей голове - это классическое сито Эратосфена и алгоритм гигантского шага по детскому шагу для дискретного логарифма над конечной группой.
источник