[Raul C]

Muy buenas, necesito ayuda con la complejidad temporal de estos 2 problemas que me están volviendo loco.

Primero:
BUSCA SUBMATRICES: Dada una matriz \( M \) de \( n \times n \) posiciones y un número \( k \), devuelve CIERTO si existe una submatriz de \( M \), con las y columnas contiguas, tal que la suma de sus elementos sea igual a \( k \), FALSO en caso contrario.
Para recorrer una matriz n x n esta claro que hace falta \( 2 \) bucles anidados, lo cual la complejidad se que es \( O(n^2) \) pero lo que pie no se como aumenta la complejidad, mi intuición me dice que es \( O(n^3) \)

Segundo:
SUMA MATRIZ: Dada una matriz de \( n \times n \) posiciones, devuelve CIERTO si la suma de los elementos de alguna fila o columna es igual a la suma del resto de elementos de toda la matriz (excepto esa columna), FALSO en caso contrario.
Para recorrer una matriz \( n \times  \)n esta claro que hace falta 2 bucles anidados, lo cual la complejidad se que es \( O(n^2) \), y aquí parece que solo necesitamos sumar toda la matriz, y después ir comparando dicha suma con los elementos de alguna fila o columna.
Hay que recorrer \( 2 \) veces, una para sumar y otra para comparar, lo cual da \( O(n^2) \), como os parece?

Un saludo y gracias a todos.

[martiniano]

Hola.

Primero:
BUSCA SUBMATRICES: Dada una matriz \( M \) de \( n \times n \) posiciones y un número \( k \), devuelve CIERTO si existe una submatriz de \( M \), con las y columnas contiguas, tal que la suma de sus elementos sea igual a \( k \), FALSO en caso contrario.
Para recorrer una matriz n x n esta claro que hace falta \( 2 \) bucles anidados, lo cual la complejidad se que es \( O(n^2) \) pero lo que pie no se como aumenta la complejidad, mi intuición me dice que es \( O(n^3) \)

No estoy seguro de haberlo entendido bien. ¿La \[ y \] es una de las entradas del algoritmo y tienes que averiguar si hay \[ y \] columnas contiguas con la misma suma?

En ese caso no veo que el coste sea mayor que el de recorrer la matriz, es decir, para mí es \[ O(n^2) \].

Utiliza una variable "suma" donde almacenes la suma de la última columna que hayas leído. Al calcular la suma de una nueva columna la comparas con "suma", si el valor coincide incrementas una variable "contador" y si ésta es igual a "y" devuelves CIERTO. Si la suma de la nueva columna no coincide con "suma" actualizas "suma" y "contador" . Si después de recorrer toda la matriz no ha finalizado el programa devuelves FALSO.

Segundo:
SUMA MATRIZ: Dada una matriz de \( n \times n \) posiciones, devuelve CIERTO si la suma de los elementos de alguna fila o columna es igual a la suma del resto de elementos de toda la matriz (excepto esa columna), FALSO en caso contrario.
Para recorrer una matriz \( n \times  \)n esta claro que hace falta 2 bucles anidados, lo cual la complejidad se que es \( O(n^2) \), y aquí parece que solo necesitamos sumar toda la matriz, y después ir comparando dicha suma con los elementos de alguna fila o columna.
Hay que recorrer \( 2 \) veces, una para sumar y otra para comparar, lo cual da \( O(n^2) \), como os parece?

.

Sí. Eso es. Recorrer la matriz dos veces no incrementa el orden del coste computacional.

Un saludo.

[Raul C]

Del a partado 1, no he copiado bien:

BUSCA SUBMATRICES: Dada una matriz M de n x n posiciones y un numero k, devuelve CIERTO si existe una submatriz de M, con las filas  y columnas contiguas, tal que la suma de sus elementos sea igual a k, FALSO en caso contrario.

No hay ninguna "y" es solo la unión de la frase.

un saludo

[martiniano]

Hola.

Del a partado 1, no he copiado bien:

BUSCA SUBMATRICES: Dada una matriz M de n x n posiciones y un numero k, devuelve CIERTO si existe una submatriz de M, con las filas  y columnas contiguas, tal que la suma de sus elementos sea igual a k, FALSO en caso contrario.

Pues es perfectamente posible que sea \[ O(n^3) \], o incluso \[ O(n^2) \], pero a mí no se me ha ocurrido ningún algoritmo que baje de \[ O(n^4) \].

Un saludo.

[Raul C]

Algoritmo de 0(n^4) ese cual es?
Yo simplemente he hecho 3 bucles anidados, pero 4? donde? como?

un saludo.

[martiniano]

Hola.

Es posible que haya algoritmos \[ O(n^3) \]. Que yo no lo haya encontrado no quiere decir que no exista. Simplemente que yo no lo he encontrado. 

Los algoritmos en los que pensé yo no mejoraban el de calcular la suma de los elementos de cada una de las submatrices con filas y columnas contiguas.

Fíjate en que el número de esas submatrices es del orden \[ O(n^4) \], ya que debemos elegir la fila en la que empieza la submatriz y la fila en la que acaba (puede ser la misma) de un total de n filas. Eso se puede hacer de \[ \binom{n} {2}+n \] maneras, el mismo número que para escoger las columnas de inicio y fin. Al multiplicar ambas cantidades te queda un polinomio de grado 4.

Si te genera dudas tu algoritmo súbelo y lo miramos.

Un saludo.

[Raul C]

La verdad es que no he hecho el algoritmo, sino simplemente he deducido que al recorrer los 3 bucles para recorrer todo, la complejidad era al menos de 3, pero es evidente que puede ser mayor.

Gracias por tus respuestas.

[martiniano]

Hola.

Yo lo que veo es que un algoritmo que resuelva el problema necesita leer todos los elementos de la matriz al menos una vez, por tanto su coste será, al menos, del orden de \[ O(n^2) \]. Por otro lado, el algoritmo que calcula las sumas de todas las submatrices es del orden de \[ O(n^4) \], por tanto el coste de cualquier algoritmo razonable será, como mucho del orden de \[ O(n^4) \]. Por ahora desconozco si hay o no hay algoritmos para este problema de orden inferior a \[ O(n^4) \], aunque lo veo perfectamente posible.

Un saludo.