Costo computazionale del problema di trasporre una matrice quadrata

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
mrzmsc
Prode Principiante
Messaggi: 5
Iscrizione: sabato 3 aprile 2021, 16:06
Sesso: Femminile

Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da mrzmsc »

Ciao a tutti, studiando per un test ho incontrato la seguente domanda:

Il problema di trasporre una matrice quadrata ha costo computazionale (nella dimensione dell'input):
  • quadratico
  • logaritmico
  • costante
  • lineare

In base alle mie conoscenze mi verrebbe da dire che la risposta corretta sia "quadratico" ma in alcune soluzioni ho trovato "lineare"... non riesco a capirne il motivo
Qual è la risposta corretta e per quale motivo?
Avatar utente
Actarus5
Prode Principiante
Messaggi: 218
Iscrizione: mercoledì 3 luglio 2013, 17:15
Desktop: Mate
Distribuzione: Fedora
Località: Abutalabashuneba

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da Actarus5 »

Diciamo che dipende un po' dal contesto, esistono algoritmi in place per il calcolo della trasposta che "aggirano" il problema accedendo agli elementi in un ordine diverso ad esempio oppure altre soluzioni tipo questa, ma sono cose sofisticate rispetto al tipo di domanda immagino, per cui mi verrebbe da rispondere quadratico anche a me.
In che senso in alcune soluzioni hai trovato lineare come soluzione? Sicuro che non ci fossero condizioni diverse sulla matrice?
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
mrzmsc
Prode Principiante
Messaggi: 5
Iscrizione: sabato 3 aprile 2021, 16:06
Sesso: Femminile

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da mrzmsc »

No la domanda era soltanto quella che ho scritto, senza ulteriori precisazioni.
Nel caso degli algoritmi in place a cui ti riferisci il costo sarebbe migliore di quello quadratico?
Credo che la domanda di riferisca all'algoritmo più efficiente in grado di risolvere il problema in questione.
Avatar utente
Actarus5
Prode Principiante
Messaggi: 218
Iscrizione: mercoledì 3 luglio 2013, 17:15
Desktop: Mate
Distribuzione: Fedora
Località: Abutalabashuneba

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da Actarus5 »

Sì, puoi leggere qui ad esempio: https://en.wikipedia.org/wiki/In-place_ ... e_matrices .
Comunque avrai fatto un corso prima del test no? Se non avete mai parlato di questo genere di algoritmi, e visto il tipo di domanda non credo, io dubito ti sia richiesto di conoscerli, per cui la risposta si dovrà basare su quello che avete visto voi a lezione.
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
mrzmsc
Prode Principiante
Messaggi: 5
Iscrizione: sabato 3 aprile 2021, 16:06
Sesso: Femminile

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da mrzmsc »

Scusami, credo mi manchi un passaggio o forse non ho capito qualcosa (sono in fase di studio)... ma l'algoritmo mostrato nel link non ha esattamente un costo quadratico O(n^2)? Mi sbaglio?
Avatar utente
Actarus5
Prode Principiante
Messaggi: 218
Iscrizione: mercoledì 3 luglio 2013, 17:15
Desktop: Mate
Distribuzione: Fedora
Località: Abutalabashuneba

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da Actarus5 »

Hai letto tutto il paragrafo?
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
mrzmsc
Prode Principiante
Messaggi: 5
Iscrizione: sabato 3 aprile 2021, 16:06
Sesso: Femminile

Re: Costo computazionale del problema di trasporre una matrice quadrata

Messaggio da mrzmsc »

Sì...
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 12 ospiti