Tengo una matriz de enteros, y necesito un algoritmo O (n) para encontrar si la matriz contiene un número y su cuadrado; un par es suficiente.Algoritmo para encontrar un número y su cuadrado en una matriz
traté de hacerlo yo mismo, pero sólo han logrado encontrar una solución en O (n 2 ).
Pensé en usar el tipo de conteo, pero el uso de la memoria es demasiado grande.
crear una nueva matriz dos veces la longitud de la matriz de entrada. O (2 N)
copia todos los números en O (N)
copiar los cuadrados de los números en O (N)
radix sort (podemos ya que son todos enteros) O (N)
iterar sobre una vez para ver si hay dos números el mismo uno después del otro O (N)
¡ganancia! O (1)
tenga en cuenta que no puede hacer esto si copia en las raíces cuadradas de las entradas porque la ordenación de radix solo funciona con enteros. los cuadrados de los enteros son enteros, entonces esto está bien. –
Es, por supuesto, innecesario copiar las raíces cuadradas Y cuadrados. Y definitivamente tendría más sentido copiar cuadros o raíces cuadradas perfectas. – nlucaroni
eso es lo que dije ... –
Si la matriz no está ordenada, no podrá hacer O (n).
Si se clasifica, se puede hacer uso de esa propiedad para hacerlo en una sola pasada, así:
foreach e in array
if squares contains e
return true
remove all less than e from squares
add e * e to squares
return false
Dónde squares es, digamos, un HashSet.
Si no está ordenado, puede ordenarlo en O (n log n) y luego utilizar este método para buscar cuadrados, que seguirán siendo más rápidos que la solución ingenua en un conjunto de datos lo suficientemente grande.
bueno, si el algoritmo está ordenado, entonces es muy fácil hacerlo en O (n). Ordenar la matriz en O (n log n) no ayudará ya que eso significa que el algoritmo completo es O (n log n) en el buen caso. – gillyb
Existen básicamente dos formas de hacerlo.
Ordene la matriz y luego realice una búsqueda binaria para el cuadrado de cada número. La complejidad general sería O (nlogn), pero necesitaría clasificación que destruiría el orden original (que podría ser importante para su caso).
Inserte todos los elementos de la matriz en una tabla hash (o cualquier estructura de datos set rápida). Luego itere sobre los elementos de la matriz nuevamente, verificando si su cuadrado existe en la tabla hash. Usar una tabla hash proporciona una complejidad general de O (n), pero necesitará O (n) espacio adicional. También puede usar un árbol basado en set (por ejemplo, std::set en C++ o TreeSet en Java), lo que le daría una complejidad de O (nlogn).
Si entiendo correctamente el problema, debe verificar si hay un número especificado en la matriz. Y no encontrar todos los números en la matriz que tienen su cuadrado en la matriz también. Simplemente mantenga dos booleanos (uno para comprobar si se ha encontrado el número, otro para el cuadrado), repita los elementos en la matriz y pruebe cada elemento. Devuelve el AND de los dos booleanos.
En pseudocódigo:
bool ArrayContainsNumberAndSquare(int number, int[] array):
boolean numberFound, squareFound;
int square = number * number;
foreach int i in array
(
numberFound = numberFound || i == number;
squareFound = squareFound || i == square;
)
return numberFound && squareFound;
No, por lo que yo entiendo, el OP está buscando cualquier par de número/cuadrado que esté en la matriz – Kena
Aunque no puedo añadir a las sugerencias anteriores, se puede reducir el tiempo promedio de carreras mediante la búsqueda de la primera valores mínimo y máximo en el conjunto de datos (tanto O (n)) y limitando tu búsqueda a ese rango. Por ejemplo, si el valor máximo es 620, sé que ningún número entero de 25 o más tiene un cuadrado en la lista.
Si se nos permite tomar que la entrada se puede clasificar en O (N) por Radix sort, me gustaría mejorar un poco en la solución de Chris:
Cada uno de los dos "punteros" es móviles estrictamente hacia adelante, por lo que la complejidad global es O (N), suponiendo que el radix tipo es O (N) y que elevar al cuadrado y la comparación son O (1). Es de suponer que quien formuló la pregunta pretendía que se hicieran estas suposiciones.
En respuesta a un comentario de la pregunta en otra respuesta: si los números enteros en la entrada no están acotadas, entonces no creo que se puede hacer. Sólo calcular el cuadrado de un entero mayor que requiere tiempo lineal (al menos: no algoritmo lineal para la multiplicación se conoce), por lo que considera una entrada de tamaño n bits, que consta de dos números enteros de tamaño n/3 bits y 2 * n/3 bits. Probar si uno es el cuadrado del otro no se puede hacer en O (n). Creo. Podría estar equivocado.
Le di a esta publicación un -1 porque confunde la definición 'normal' de tamaño de 'entrada'. En los modelos de computación RAM "estándar", se supone que los enteros son lo suficientemente pequeños (o los registros son lo suficientemente grandes) para caber en registros O (1), y MUL/DIV, etc. son O (1). –
Aunque indiqué qué suposiciones se hicieron para dar una solución O (N). He agregado que el profesor presumiblemente pretendía que se hicieran. ¿Hay algo más que agregue para que esto no cause confusión? –
Cuando juzgamos la complejidad temporal de los algoritmos, consideramos las multiplicaciones (et al.) Como operaciones únicas. Luego, el algoritmo se evalúa según la cantidad de operaciones necesarias para completar (o, más exactamente, cómo crece el número de operaciones a medida que crece el tamaño de la entrada). –
Usted puede ser capaz de hacerlo con un par de hashsets ayudar a salir.
Mientras que la iteración, Si el valor está en la hashset cuadrados, tienes un par (el valor es el cuadrado de un valor previamente encontrado) Si la plaza está en los valores hashset, tienes un par (el cuadrado de este valor ya se pasó) else almacena el valor en uno y el cuadrado en el otro.
Personalmente, creo que la respuesta de Anon (el pequeño algoritmo con 'cuadrados') es más útil de lo que parece: elimine la línea 'quitar todo menos e de cuadrados' y el algoritmo puede manejar un ordenado matriz de entrada.
Si asumimos la máquina típica de tareas con espacio suficiente, la estructura de datos 'plazas' podría modelarse como una matriz de indicadores booleanos, produciendo un verdadero tiempo de búsqueda O (1).
Si usamos entradas sin signo C/C++ de 32 bits, el valor máximo que se puede almacenar es: 4294967295 = (2 < < 32) -1. El número más grande cuyo cuadrado podemos almacenar es (1 < < 16) -1 = 65535. Ahora, si creamos una matriz de bits y almacenamos en la matriz, ya sea que hayamos visto el número y/o su cuadrado (2 bits por "ranura"), podemos obtener el almacenamiento total en 65535/4 = 16384 bytes.
OMI Esto no es el consumo excesivo de memoria por lo que debemos ser capaces de hacer esto sin clasificación radix. Un O (N) algoritmo podría tener este aspecto:
uint32_t index(uint32_t i) { return i/4; }
unsigned char bit1(uint32_t i) { return 1<<((i%4)*2); }
unsigned char bit2(uint32_t i) { return 1<<((i%4)*2 +1); }
bool hasValueAndSquare(std::vector<uint32_t> & v)
{
const uint32_t max_square=65535;
unsigned char found[(max_square+1)/4]={0};
for(unsigned int i=0; i<v.size(); ++i)
{
if (v[i]<=max_square)
{
found[ index(v[i]) ] |= bit1(v[i]);
if ((found[ index(v[i])] & bit2(v[i])) == bit2(v[i])) return true;
}
uint32_t w = (uint32_t)round(sqrt(v[i]));
if(w*w == v[i])
{
found[ index(w) ] |= bit2(w);
if ((found[index(w)] & bit1(w)) == bit1(w)) return true;
}
}
return false;
}
Esto no se ha probado, no muy optimizado, y un número entero adecuado de raíz cuadrada sería mejor. , sin embargo, el compilador debe alinear todas las funciones de acceso a bit, para que estén bien.
Tenga en cuenta que si estamos usando 64 bits enteros el consumo de memoria se convierte en mucho más grande, en lugar de una serie de 16Kb necesitamos una matriz de 1 Gb - menos práctico posible.
1) Con el hashmap obtienes O (n).
2) Si utiliza std :: set en 2 conjuntos: los iguala, y las probabilidades, puede obtener
2 * O (n/2() log (n/2)) = O (n log (n/2))
suponiendo que hay más o menos tantas probabilidades que iguala
Sin clasificar, trabaja con los duplicados:
Iterar la matriz para encontrar los números enteros más grandes y más pequeñas. O (n)
Crea una matriz de bits del tamaño de la diferencia. O (1) tiempo, O (k) espacio
(Ahora cada posible número entero entre los valores más pequeños y más grandes tiene un bit correspondiente en el array)
Iterar el viejo-array, establecer el bit correspondiente a cada entero encontrado en 1. O (n)
Vuelva a iterar la matriz anterior, verificando si el cuadrado del entero tiene su bit correspondiente. O (n)
(Aunque no Ordena, este algoritmo puede ser fácilmente modificado para crear a sorting algorithm que ordena en O (n + k) el tiempo y el espacio O (k))
Por supuesto, en la vida real esto es O (n + k), ya que necesita poner a cero la matriz; pero generalmente no consideramos cosas así cuando definimos algoritmos. Esta es muy probablemente la respuesta "correcta". –
"normalmente no consideramos cosas así". Algunos de nosotros lo hacemos, algunos de nosotros no. Por ejemplo, al observar la complejidad de un algoritmo para ISPRIME, O (n + k) sería un desastre, ya que k es aproximadamente 2^n. Todo depende del contexto, y nunca habiendo estudiado CompSci en una universidad, no puedo adivinar qué supuestos se habrían expresado en la conferencia, pero no en esta pregunta ... –
@Steve: quise considerar cosas como cuánto tiempo lleva a cero una matriz. Por supuesto, 'k' es un factor importante en la mayoría de los otros casos.Sin embargo, desde un punto de vista de algoritmos, una matriz puede ser * "declarada" * como puesta a cero en O (1), por lo que en este caso 'k' no se cuenta como parte de la complejidad (un ejemplo del mundo real: una matriz podría, teóricamente, ponerse a cero en hardware con un simple interruptor en ** O (1) **; no conozco ninguna computadora que realmente implemente esto). –
notas de optimización
Tanto los algoritmos hashset y radix sort pueden ser optimizados por señalar tres hechos:
El optimizados los algoritmos que se muestran a continuación suelen ser 5 veces más rápidos y utilizan menos de la mitad de la RAM del caso no optimizado. En algunos casos, cuando el tamaño de los datos es similar al tamaño de caché L2/L3, pueden realizarse 100 veces más rápido o más.
algoritmo optimizado basado en radix tipo
estructura de datos es cinco listas de números enteros: IN, AODD, Bodd, Apar, Beven El listas A y B utilizan la mitad del tamaño entero de IN. (Por ejemplo, si EN = 64bits, Un & B = 32bits)
Si cualquiera de exploración lineal encuentra una coincidencia, devuelve ese partido inmediatamente.
La razón de que esto es mucho más rápido que el algoritmo radix tipo sencillo que es:
algoritmo optimizado basado en hashset
estructura de datos es la lista de números enteros en, además de dos hashsets a y B el Los conjuntos A y B usan la mitad del tamaño entero e de IN
la razón de que esto es más rápido que el algoritmo hashset sencillo es que:
Hay una pequeña optimización adicional disponible aquí: A y B puede ser un solo hashset, que almacena bandera de bits con cada entrada para decir si el entero es en A o B (que puede No estar en ambos porque entonces el algoritmo habría terminado).
¿Se puede usar espacio extra? Intenta pensar cómo podrías usarlo. –
Publicar lo que ya has intentado sería agradable. De esa forma podríamos ver qué tan cerca está de una solución. –
La pregunta no establece una limitación específica en el espacio, pero creo que debería ser razonable. – gillyb