[Algo] Progettare un semplice algoritmo

[Pablitos23]

L'algoritmo deve trovare in una matrice, un elemento che sia il massimo della sua colonna e il minimo della sua riga.
La mia prima idea ha una complessità pari a $O(n^3)$ nel caso peggiore, ossia per ogni elemento della matrice prima controllo che sia il minimo della sua riga e dopo che sia anche il massimo della sua colonna. Verificate le due condizioni ritorno gli indici dell'elemento.

Avete in mente qualche algoritmo più efficiente?

Ciao

[apatriarca]

Esistono un solo elemento minimo e un solo elemento massimo per ogni riga/colonna. Per cui non è necessario fare la verifica per ogni elemento della matrice. Per ogni riga cerchi il suo minimo e una volta trovato controlli se questo elemento è il massimo della sua colonna. Per cui alla fine hai un algoritmo che è \(O(n^2)\). Non credo si possa fare di meglio a livello di complessità asintotica. Per trovare il massimo o il minimo di ogni riga o colonna hai infatti bisogno di visitare una volta tutti gli elementi della matrice per cui credo che \(O(n^2)\) sia minimale in questo caso.