¿Cuál es el tiempo O para determinar si un valor está en una matriz ordenada?
-
19-08-2019 - |
Pregunta
Tengo una matriz ordenada de 5000 enteros. ¿Qué tan rápido puedo saber si un entero aleatorio es miembro de la matriz? Una respuesta en general, C y Ruby estarían bien.
Los valores de la matriz tienen la forma
c * c + 1
donde c
puede ser cualquier número entero de 1 a 5000.
Por ejemplo:
[2, 5, 10, 17, 26, 37, 50 ...]
Solución
La búsqueda binaria, como han mencionado otros, es O (log2N), y puede codificarse de forma recursiva:
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = (low + high) / 2
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
o iterativamente:
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
Sin embargo, si está buscando la forma más rápida posible, puede configurar una tabla de búsqueda basada en el sqrt (N-1)
de sus números. Con solo 5,000 palabras de memoria puede lograr búsquedas O (1) de esta manera.
Explicación:
Dado que todos sus números tienen la forma N ^ 2 + 1 para un entero N de 1 a N, puede crear una tabla de N elementos. El elemento en la posición i especificará si i ^ 2 + 1 está en su matriz o no. La tabla se puede implementar con una matriz simple de longitud N. Se necesitará O (N) para construir y N palabras de espacio. Pero una vez que tenga la tabla, todas las búsquedas son O (1).
Ejemplo:
Aquí está el código de muestra en Python, que se lee como pseudocódigo, como siempre :-)
import math
N = 5000
ar = [17, 26, 37, 50, 10001, 40001]
lookup_table = [0] * N
for val in ar:
idx = int(math.sqrt(val - 1))
lookup_table[idx] = 1
def val_exists(val):
return lookup_table[int(math.sqrt(val - 1))] == 1
print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)
La construcción de la tabla ocupa O (N) como máximo, y las búsquedas son O (1).
Otros consejos
log (n) para búsqueda binaria en c
¡Diría que es O (const)! :)
Dado un número aleatorio r, es trivial verificar si es un número que podría representarse en la forma (n * n + 1). ¡Solo verifique si el sqrt (r-1) es un entero o no!
(Bueno, podría ser un poco más complicado que eso, ya que su lenguaje de programación puede introducir cierta complejidad al tratar con números enteros frente a números de coma flotante, pero aún así: no necesita buscar la matriz en absoluto: solo verifique si el número está en esta forma particular.)
Técnicamente, la complejidad de encontrar un elemento en una matriz de tamaño fijo es constante, ya que log 2 5000 no va a cambiar.
La búsqueda binaria es O (log n)
O (log n) si la matriz tiene n elementos
Solo para ampliar eso: son lg n pruebas, es decir log 2 n. Eso lo convierte en O ( registro n) . ¿Por qué? porque cada prueba de una búsqueda binaria divide la matriz a la mitad; por lo tanto, toma lg n pruebas.
Usando una búsqueda binaria, es el tiempo de búsqueda de Log (N).
bool ContainsBinarySearch(int[] array, int value) {
return Array.BinarySearch(arrray, value) >= 0;
}
En Perl:
Cargaría los valores en un hash estático y luego sería O (1).
Construir el hash de búsqueda
lookup_hash {$ _} = 1 foreach (@original_array);
Sintaxis de búsqueda
($ lookup_hash {$ lookup_value}) & amp; & amp; print " Lo encontré en O (1) - no hay bucle aquí \ n " ;;