Costo computazionale del problema di trasporre una matrice quadrata

di mrzyasha il
5 risposte
Pochi posts
Iscritto da
mag, 2020
Messaggi
29

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?

5 Risposte

  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    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)
  • Pochi posts
    Iscritto da
    mag, 2020
    Messaggi
    29
    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?
  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    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)
  • Pochi posts
    Iscritto da
    mag, 2020
    Messaggi
    29

    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?

  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221

    N e n non sono la stessa cosa

Devi accedere o registrarti per scrivere nel forum
5 risposte