Matrice di Boolean

[carota89]

Ciao a tutti, qualcuno mi sa spiegare la rioluzione di questi 2 esercizi sulla matrice di Boolean:

1° ES:
Data una matrice di Boolean quadrata con n righe, si consideri il problema di determinare
se ha una struttura a scacchiera dei segni. Quale delle seguenti asserzioni risulta vera?

(a) Esiste un algoritmo con complessita O(n log n);
(b) L'algoritmo con massima ecienza ha complessita O(n3);
(c) Esiste un algoritmo con complessita O(n2), ma non risulta ottimo, dato che se ne
possono trovare altri con complessita minore;
(d) Esiste un algoritmo con complessita O(n2), che risulta ottimo, ovvero non se ne
possono trovare altri con complessita minore;
(e) il problema e' intrattabile.

2°Es:
Data una matrice di Boolean quadrata di dimensione n, si consideri il problema di de-
terminare se questa contiene un numero maggiore di un valore x assegnato. Quale delle
seguenti risulta vera?

(a) Esiste un algoritmo con complessita' O(n);
(b) L'algoritmo con massima effcienza ha complessita' TETA(n3);(dove teta sta ad incare l'algoritmo ottima)
(c) Esiste un algoritmo con complessita O(n2), ma non risulta ottimo, dato che se ne
possono trovare altri con complessita' minore;
(d) Esiste un algoritmo con complessita O(n2), che risulta ottimo, ovvero non se ne
possono trovare altri con complessita minore;
(e) il problema e intrattabile.

[alka]

Qui non facciamo i compiti a casa, né traduciamo o interpretiamo gli esercizi da svolgere.

Questi testi li devi approfondire con il professore, oppure cercare di analizzarli ed esporre i tuoi dubbi, su un problema singolo alla volta, indicando il linguaggio, come richiesto dal Regolamento e come ti era già stato detto qui.

Il forum è uno spazio per ricevere aiuto nella risoluzione di problemi, e non nella loro delegazione degli stessi ad altri.