¿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.
complexity-theory
asymptotics
space-complexity
vawd_gandi
fuente
fuente
Respuestas:
espacio es algo inusual; La razón más probable para que surja tal complejidad es como resultado de una llamadareunión en elesquemaintermedio.n−−√
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.
fuente