performance - una - Encontrar el número en la matriz ordenada(Filas n Columnas) en O(log n)
multiplicacion de matrices (5)
Esta pregunta ya tiene una respuesta aquí:
Supongamos que tengo una matriz ( MxN ) que tiene ordenadas sus filas y columnas.
- Todos los elementos en cada fila están ordenados en orden creciente
- Todos los elementos en cada columna están ordenados en orden creciente
- Todos los elementos son enteros
No se pueden hacer otras suposiciones
Ejemplo:
[1 5 8 20]
[2 9 19 21]
[12 15 25 30]
Tengo que encontrar si un número dado está presente en la matriz o no (Búsqueda básica). Tengo un algoritmo que ejecuta O(n)
int row = 0;
int col = N-1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
Pero me pidieron una O(log (MxN)) == O(Log(n)) . ¿¿Algunas ideas??
Creo que esto se puede hacer en O (log (n * n) * log (n)) tiempo, donde n es el no. de las filas de una matriz cuadrada.
Por las propiedades de Matrix, la diagonal principal de la matriz es una matriz ordenada. Entonces, podemos buscar un elemento o su límite inferior en O (log (n)). Ahora, usando este elemento como pivote, tenemos 4 submatrices. y podemos decir que todos los elementos en la submatriz (arriba a la izquierda) son más pequeños, todos los elementos en la submatriz (abajo a la derecha) son más grandes. Entonces, podemos eliminar eso del espacio de búsqueda.
Ahora, busque de forma recursiva en la submatriz (arriba a la derecha) y en la submatriz (abajo a la izquierda).
Dado que, en cada paso, llevamos a cabo una búsqueda de registro (n) (a lo largo de la diagonal principal), puede haber más pasos de registro (n * n) (ya que reducimos el espacio de búsqueda a la mitad en cada paso).
Entonces, la complejidad del tiempo = O (log (n) log (n n)).
Por favor, corrige, si algo está mal.
Refrences - [Libro] descifrando la entrevista de codificación (Pregunta 11.6)
Dado que ambas filas y columnas están ordenadas, si miramos el primer elemento de cada fila, podemos encontrar cuál contiene el número que estamos buscando. Entonces, de nuevo, podemos aprovechar el hecho de que los elementos en cada fila están ordenados y encontrar ese número.
El algoritmo de búsqueda más rápido que conozco es Búsqueda Binaria, que tiene una complejidad de O (log n), por lo que la complejidad total será O (log m + log n).
Aquí hay un ejemplo, supongamos que estamos buscando 28:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
- Hacemos una búsqueda binaria sobre los elementos de la primera columna (1, 11, 21, 31, 41) y encontramos que la fila es la tercera, porque su primer elemento es más pequeño que nuestro número, pero el primer elemento de la siguiente fila es más grande. Número de pasos: 2 (21, 31, encontrado)
- Hacemos una búsqueda binaria nuevamente en la tercera fila (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) y encontramos nuestro número. Número de pasos: 2 - 3 (25, 27 o 28, encontrados)
La solución O (log (M * N)) no es posible para esta tarea.
Veamos una tarea simplificada: en matriz cuadrada "ordenada", asuma todos los elementos por encima de la diagonal secundaria (verde) menor que el número dado, todos los elementos debajo de la diagonal secundaria (rojo) mayor que el número dado, y sin suposiciones adicionales para los elementos en la diagonal secundaria amarillo).
Ni los supuestos originales de esta tarea, ni estas suposiciones adicionales nos dicen cómo los elementos en la diagonal secundaria están relacionados entre sí. Lo que significa que solo tenemos una matriz desordenada de N enteros. No podemos encontrar el número dado en la matriz no ordenada más rápido que O (N). Entonces, para el problema original (más complicado) con la matriz cuadrada, no podemos obtener una solución mejor que O (N).
Para una matriz rectangular, estire la imagen cuadrada y establezca los supuestos adicionales en consecuencia. Aquí tenemos sub-arreglos ordenados mínimos (N, M) de tamaño max (N, M) / min (N, M) cada uno. La mejor manera de buscar aquí es usar la búsqueda lineal para encontrar uno o varios sub-arreglos que puedan contener un valor dado, luego para usar la búsqueda binaria dentro de estos sub-arreglos. En el peor de los casos, es necesario realizar una búsqueda binaria en cada subarreglo. La complejidad es O (min (N, M) * (1 + log (max (N, M) / min (N, M)))). Entonces, para el problema original (más complicado) con la matriz rectangular, no podemos obtener una solución mejor que O (min (N, M) * (1 + log (max (N, M)) - log (min (N, M))) )
No es posible hacer mejor que O (n). Algunos chicos (hay al menos tres de ellos en esta página) creen que pueden hacerlo mejor, pero eso se debe a que sus algoritmos son incorrectos o porque no saben cómo calcular la complejidad de su algoritmo, por lo que intentan adivinarlo. Esta publicación de blog es muy buena y te explicará los errores de estos tipos.
Borrador de una prueba de que O (n) es óptimo: considere la siguiente matriz:
1 2 3 4 5 6 … (n-2) (n-1) (n+1)
2 3 4 5 6 7 … (n-1) (n+1) (n+2)
3 4 5 6 7 8 … (n+1) (n+2) (n+3)
… … … … … … … … … …
(n-2) (n-1) … … … … … … … (2n-1)
(n-1) (n+1) … … … … … … … 2n
(n+1) (n+2) … … … … … (2n-1) 2n (2n+1)
Si está buscando n en esta matriz, debe verificar al menos una vez para cada fila si n está en la fila porque n podría estar en cualquier fila. (La prueba no está completa pero esta es la idea)
Tienes que usar recursión para resolver este problema. Dada una matriz X y un número y, puede hacer una búsqueda binaria para y en la fila central de X y dividir la matriz en cuatro partes de manera que:
A|B
---
C|D
todos los elementos en A son menores que y, todos los elementos en D son mayores que y, e y puede estar en B y C. Encuentra iterativamente y en B y C.
Desde altura (A) = altura (B) / approx = altura (C) = altura (D), tamaño (X)> = 2 * (tamaño (B) + tamaño (C)). Entonces, la complejidad resultante es O (logn).
def find(X,y):
a,b = X.shape
i = a /2
j = binsearch(X[i,:], y)
if X[i,j]==y:
return True
else:
return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )