Costo computazionale del problema di trasporre una matrice quadrata

5 Risposte

• 

  Weierstrass

  Utente Famoso

  Iscritto da

  feb, 2019

  Messaggi:

  2245

  Re: Costo computazionale del problema di trasporre una matrice quadrata

  17 nov 2022, 16:43

  La domanda è evidentemente mal posta e si presta ad ambiguità.
  
  Se la trasposizione è obbligatoriamente fisica (perché se, banalmente, inverti gli indici avrai un costo O(1) costante), se per dimensione dell'input si intende il numero di elementi della matrice (N = n x n) e se vuoi sapere il costo computazionale di un algoritmo ottimale (con un algoritmo qualsiasi potresti fare le peggio cose) nel worst case (elementi della matrice tutti differenti tra loro), allora la soluzione è lineare (in N)
• M

  mrzyasha

  Pochi posts

  Iscritto da

  mag, 2020

  Messaggi:

  29

  Re: Costo computazionale del problema di trasporre una matrice quadrata

  17 nov 2022, 21:20

  Ciao e intanto ti ringrazio per la risposta.
  Condivido con te che la domanda sia poco chiara ma credo che le tue deduzioni siano tutte giuste.
  
  Posso chiederti come sei arrivato alla soluzione?
• 

  Weierstrass

  Utente Famoso

  Iscritto da

  feb, 2019

  Messaggi:

  2245

  Re: Costo computazionale del problema di trasporre una matrice quadrata

  17 nov 2022, 23:20

  Nel worst case scambierai tutti gli elementi tranne quelli sulla diagonale principale: il numero di scambi sarà quindi gli elementi totali (N=n^2) meno gli elementi sulla diagonale principale (n) diviso 2.
  
  O((n^2-n)/2) = O(n^2-n) = O(n^2) = O(N)
• M

  mrzyasha

  Pochi posts

  Iscritto da

  mag, 2020

  Messaggi:

  29

  Re: Costo computazionale del problema di trasporre una matrice quadrata

  19 nov 2022, 13:12

  Ok comprendo il tuo ragionamento e ti ringrazio, tranne l'ultimissimo passaggio.

  Da O(n^2) non si può passare a O(n), o sbaglio? L'elevamento al quadrato non è un semplice coefficiente irrilevante, ma stabilisce proprio l'ordine di grandezza…

  Quindi la risposta corretta sarebbe quadratico, giusto?

• 

  Weierstrass

  Utente Famoso

  Iscritto da

  feb, 2019

  Messaggi:

  2245

  Re: Costo computazionale del problema di trasporre una matrice quadrata

  20 nov 2022, 22:30

  N e n non sono la stessa cosa