Matrice di Boolean

[icarota]

Matrice di Boolean
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.

[!fazz]

chiedi qui

http://www.hwupgrade.it/forum/showthread.php?t=1321413

[Marinelli]

Discussione chiusa, ciao.