Algoritmos con complejidad O (sqrt (N)) ESPACIO?

13

¿Hay algún algoritmo conocido para problemas formulados que requiera una complejidad ESPACIO de O (sqrt (N))? Sé que existen algoritmos con esa gran complejidad de tiempo.

vawd_gandi
fuente
Para un problema importante llamado 3sum, existe la siguiente compensación. Si desea tiempo , la complejidad espacial más conocida es . Ver arxiv.org/abs/1605.07285O(norte2)O(norte)
eig

Respuestas:

15

espacio es algo inusual; La razón más probable para que surja tal complejidad es como resultado de una llamadareunión en elesquemaintermedio.norte

Dos ejemplos notables en la parte superior de mi cabeza son el tamiz clásico de Eratóstenes y el algoritmo de paso gigante de paso de bebé para el logaritmo discreto sobre un grupo finito.

ordenación rápida
fuente