¿Cuál es el tiempo O para determinar si un valor está en una matriz ordenada?

Question

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 ...]

Answer 1

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).

Answer 2

log (n) para búsqueda binaria en c

Answer 3

¡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.)

Answer 4

Técnicamente, la complejidad de encontrar un elemento en una matriz de tamaño fijo es constante, ya que log ₂ 5000 no va a cambiar.

Answer 5

La búsqueda binaria es O (log n)

WikiPedia

Answer 6

O (log n) si la matriz tiene n elementos

Answer 7

Solo para ampliar eso: son lg n pruebas, es decir log ₂ 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.

Answer 8

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;
}

Answer 9

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 " ;;