Algorithmes avec complexité O (sqrt (N)) SPACE?

Existe-t-il des algorithmes connus pour les problèmes formulés qui nécessitent une complexité SPACE de O (sqrt (N))? Je sais qu'il existe des algorithmes avec cette complexité temporelle big-O.

complexity-theory asymptotics space-complexity vawd_gandi
la source

Pour un problème important appelé 3sum, il y a le compromis suivant. Si vous voulez du temps , la complexité spatiale la plus connue est

. Voir arxiv.org/abs/1605.07285

O (n^{2})

$O(n^2)$

O (\sqrt{n})

$O(\sqrt{n})$

eig

Réponses:

$\sqrt{n}$ espace est quelque peu inhabituel; la raison la plus probable pour laquelle une telle complexité émerge est le résultat d'une soi-disant rencontre dans le schéma intermédiaire .

Deux exemples notables au sommet de ma tête sont le tamis classique d'Eratosthène et l' algorithme de pas de géant à pas de bébé pour le logarithme discret sur un groupe fini.

tri rapide
la source