¿Hay algún algoritmo del orden O (sqrt (n))?

Sí, y esto no es solo un tecnicismo.

Primero los aspectos técnicos: por ejemplo, [math] O (\ sqrt {n}) [/ math] es la complejidad temporal del algoritmo ingenuo que prueba si [math] n [/ math] es primo al verificar todos los divisores de 2 a [matemáticas] \ lfloor \ sqrt {n} \ rfloor [/ math].

¿Por qué llamo al caso anterior un tecnicismo? Porque en ese caso la variable [math] n [/ math] no es el tamaño de entrada real. El tamaño de entrada es proporcional a [math] \ log n [/ math] y, por lo tanto, el algoritmo anterior ni siquiera es polinómico en el tamaño de entrada.

Pero incluso si [math] n [/ math] en su pregunta es el tamaño de entrada, la respuesta sigue siendo “sí”. Hay bastante teoría detrás de los algoritmos que usan una cantidad sublineal de tiempo y / o espacio. Tales algoritmos en realidad pueden hacer muchas cosas útiles.

Por ejemplo, suponga que tiene una colección de elementos. El número de elementos es [matemática] n [/ matemática], y [matemática] n [/ matemática] es realmente muy grande. Una pregunta que puede hacer es si todos los elementos de su colección son distintos. Obviamente, la complejidad de tiempo en el peor de los casos de cualquier algoritmo exacto debe ser lineal, ya que debe examinar todos los elementos para asegurarse de que la respuesta sea “sí, todos son distintos”. Aún así, podemos hacer algo útil en tiempo sublineal: con alta probabilidad podemos distinguir dos situaciones que son suficientemente distintas. En particular, podemos distinguir los siguientes dos casos:

• todos los elementos [math] n [/ math] son ​​distintos
• el número de elementos distintos es como máximo [matemática] (1- \ varepsilon) n [/ matemática] (es decir, los duplicados forman al menos una pequeña fracción constante de la población)

¿Cómo podemos hacer eso? Resulta que el muestreo inteligente [math] O (\ sqrt {n}) [/ math] elementos de la población es suficiente. La intuición detrás de la prueba está estrechamente relacionada con la paradoja del cumpleaños. Para más detalles, vea la lección 1 en 6.893 Materiales.

Se puede resolver un algoritmo simplista para la consulta de rango mínimo / máximo (RMQ) usando O (sqrt (n)). http://community.topcoder.com/tc …

Un algoritmo básico para la factorización de enteros pasa por números del 2 al sqrt (n) para encontrar los factores primos de n.

El algoritmo de paso gigante de Baby-step utiliza una técnica de encuentro en el medio para resolver el problema del logaritmo discreto. El problema pregunta, dados los enteros a, byn, encontrar todas las x de manera que a ^ x = b módulo n

El algoritmo de Grover es un algoritmo cuántico para buscar una base de datos no ordenada de n entradas en tiempo O (sqrt (n)).

sqrt (n) es el número que minimiza la función max (k, n / k) que resulta útil en algunos problemas de algoritmos. Aquí hay un artículo que escribí sobre esta idea en particular Byte del concurso de codificación: El truco de la raíz cuadrada

Sí, y puedo probar esto con un ejemplo:

Si desea verificar la primalidad de un número, solo necesita buscar factores que sean menores o iguales a la raíz cuadrada del número dado.

Por ejemplo: para verificar la primalidad de 100:

Los posibles factores son:

2 * 50

4 * 25

5 * 20

10 * 10

20 * 5

25 * 4

50 * 2

Observe cómo los factores A * B se convierten en B * A después de la raíz cuadrada, es decir, 10

Esto se aplica a todos los números positivos que hacen la complejidad como O (√n).

Los hay, pero a veces pueden ser extraños. Recuerde que esto significa que este algoritmo debe mirar solo una porción muy pequeña de su entrada. Ni siquiera puede mirar cada elemento.

Un ejemplo particularmente interesante es el algoritmo de Grover, que permite la búsqueda (en contexto cuántico) en una entrada no ordenada en tiempo proporcional a la raíz cuadrada del tamaño de la entrada.

Si.

Michal Forišek es perfecto como de costumbre, pero me gustaría dar un ejemplo más concreto de un algoritmo que es [math] O (\ sqrt {n}) [/ math], donde [math] n [/ math] es El tamaño de su entrada.

El siguiente algoritmo salta entre un conjunto de estados enteros. La lista de entrada especifica las transiciones: si el estado actual es pos , el siguiente estado es a[pos] .

Si este proceso alcanza un estado en el que ha estado antes, a partir de ese punto repetirá la misma secuencia de pasos una y otra vez: ha alcanzado un ciclo.

El siguiente algoritmo determina si el número total de estados que se visitarán es menor que [math] \ sqrt {n} [/ math], o no. Lo hace en la mayoría de las iteraciones [math] \ sqrt {n} [/ math].

# in: una longitud n lista de estados sucesores enteros en el rango
# {0, 1, …, n-1}
# out: Verdadero si la secuencia 0, a [0], a [a [0]],… visitas
# menos que o igual a los estados sqrt (n), y Falso de lo contrario.

def not_too_many_states (a):
visitado = {0}
pos, pasos, n = 0, 1, len (a)
mientras que pasos * pasos <= n:
pos = a [pos]
si pos en visitado:
volver verdadero
visitado.add (pos)
pasos + = 1
falso retorno

La búsqueda binaria es un algoritmo bien conocido, cuya complejidad es [matemática] O (\ log n) [/ matemática], por lo tanto, también es [matemática] O (\ sqrt {n}) [/ matemática].

La búsqueda de fragmentos es uno de los primeros algoritmos que aprende un estudiante de CS, por lo general: implica buscar el primer elemento de un fragmento de tamaño n en una lista ordenada hasta que encuentra el fragmento donde probablemente está el objetivo y luego buscar ese fragmento.

En su estado óptimo, donde el tamaño del fragmento es igual a la raíz cuadrada del tamaño de la lista, la búsqueda del fragmento es un algoritmo O (sqrt (n)) .

Si tiene una red de N nodos y desea comunicar un mensaje a todos ellos en solo dos pasos, lo hace por cada nodo hablando con nodos O (sqrt (n)) en ambos pasos.

Las consultas de rango ortogonal en un árbol kd bidimensional toman tiempo O ( sqrt ( n )). (Aproximadamente, encuentre puntos que se encuentran en un rectángulo dado, fuera de un conjunto dado de n puntos).

Saltar búsqueda

Búsqueda de salto – GeeksforGeeks

Si. El ejemplo más simple:

para i en rango (sqrt (n)):
hacer algo()

Si. El tiempo de ejecución asintótico de verificar si el número es primo o no está limitado anteriormente por O (sqrt (n)).