Algorithmen mit O (sqrt (N)) SPACE-Komplexität?

Gibt es bekannte Algorithmen für formulierte Probleme, die eine SPACE-Komplexität von O (sqrt (N)) erfordern? Ich weiß, dass Algorithmen mit dieser Komplexität existieren.

complexity-theory asymptotics space-complexity vawd_gandi
quelle

Für ein wichtiges Problem namens 3sum gibt es den folgenden Kompromiss. Wenn Sie

Zeit wollen, ist die bekannteste Raumkomplexität

O (n^{2})

$O(n^2)$

. Siehearxiv.org/abs/1605.07285

O (\sqrt{n})

$O(\sqrt{n})$

eig

Antworten:

Raum ist etwas ungewöhnlich; Der wahrscheinlichste Grund für die Entstehung einer solchen Komplexität ist ein sogenanntesTreffen im mittlerenSchema. $\sqrt{n}$

Zwei bemerkenswerte Beispiele auf den ersten Blick sind das klassische Sieb des Eratosthenes und der Baby-Step-Riesenschritt- Algorithmus für den diskreten Logarithmus über eine endliche Gruppe.

schnelle Sorte
quelle