# TDA | practica 2 ejercicio 8
## Consigna
- Se tiene una matriz booleana $A$ de $n \times n$ y una operación `conjunciónSubmatriz` que toma $O(1)$ y que dados 4 enteros $i_0, i_1, j_0, j_1$ devuelve la conjunción de todos los elementos en la submatriz que toma las filas $i_0$ hasta $i_1$ y las columnas $j_0$ hasta $j_1$. Formalmente:
$$
\text{conjunciónSubmatriz}(i_0, i_1, j_0, j_1) = \bigwedge_{i_0 \leq i \leq i_1, j_0 \leq j \leq j_1} A[i, j]
$$
1. Dar un algoritmo que tome tiempo estrictamente menor que $O(n^2)$ que **calcule la posición de algún `false`, asumiendo que hay al menos uno.** Calcular y justificar la complejidad del algoritmo.
2. Modificar el algoritmo anterior para que cuente cuántos `false` hay en la matriz. Asumiendo que hay a lo sumo 5 elementos `false` en toda la matriz, calcular y justificar la complejidad del algoritmo.
3. Si obtuvo una complejidad $O(n^2)$ en el punto anterior, mejore el algoritmo y/o el cálculo para obtener una complejidad menor.
## Resolución
1. Tengo que recorer la matriz y usar conjunción submatriz que tiene tiempo constante.
2. Divido a la matriz en 4 submatrices más chicas y aplico recursivamente conjunciónSubmatriz.
3. Caso base:
- Cuando la matriz es de $1 \times 1$
- Si la posición es false devolverlo
- Else: devolver None
### Código para primer inciso
```python
import numpy as np
def posFalse(M,i_1,i_2,j_1,j_2)->bool:
# Caso base O(1)
if j_1 == j_2 and i_1 == i_2: # O sea si el tamaño de la matriz es de 1x1
if M[i_1][j_1] == False:
return (i_1,j_1)
else:
return None
# Dividir
# Calculo puntos medios en filas y columnas
i_mitad = (i_1 + i_2)//2
j_mitad = (j_1 + j_2)//2
cuadranteSupIzq = (i_1, i_mitad, j_1, j_mitad)
cuadranteSupDer = (i_1, i_mitad, j_mitad + 1, j_2)
cuadranteInfIzq = (i_mitad + 1, i_2, j_1, j_mitad)
cuadranteInfDer = (i_mitad + 1, i_2, j_mitad + 1, j_2)
# Conquistar
# Revisar cada cuadrante y buscar de forma recursiva
# el asterisco es para desempaquetar la tupla
if not conjuncionSubMatriz(M, *cuadranteSupIzq):
return posFalse(M, *cuadranteSupIzq)
if not conjuncionSubMatriz(M, *cuadranteSupDer):
return posFalse(M, *cuadranteSupDer)
if not conjuncionSubMatriz(M, *cuadranteInfIzq):
return posFalse(M, *cuadranteInfIzq)
if not conjuncionSubMatriz(M, *cuadranteInfDer):
return posFalse(M, *cuadranteInfDer)
return None
def conjuncionSubMatriz(M, i_0, i_1, j_0, j_1):
return np.all(M[i_0:i_1+1, j_0:j_1+1])
```
## Complejidad
- siendo $L = n \times n$
- $T(L) = 4T\left(\frac{L}{4}\right) + O(1)$
- $a = 4, \ b = 4$
- $\log_b(a) = \log_4(4) = 1$
- Por el teorema maestro, tenemos que:
- Si $f(L) = O(L^{\log_b a - \epsilon})$ para algún $\epsilon > 0$, entonces $T(L) = \Theta(L^{\log_b a})$.
- Si $f(L) = \Theta(L^{\log_b a})$, entonces $T(L) = \Theta(L^{\log_b a} \log L)$.
- Si $f(L) = \Omega(L^{\log_b a + \epsilon})$ para algún $\epsilon > 0$ y si $a f\left(\frac{L}{b}\right) \leq k f(L)$ para alguna constante $k < 1$ y suficientemente grande $n$, entonces $T(L) = \Theta(f(L))$.
Dado que $f(L) = O(1)$, caemos en el primer caso del teorema maestro y por lo tanto:
- $T(L) = \Theta(n^2)$.