Costo computazionale

[Fab996]

Potete dirmi il costo di questi tre metodi ?
Determinare il costo in tempo dei seguenti
metodi che calcolano la somma degli elementi
della diagonale principale di una matrice
quadrata di interi, utilizzando la notazione O

public static int sommaDiagonale1(int[][] A) {
int n = A.length;
int somma = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i == j) somma += A[i][j];
return somma;
}
public static int sommaDiagonale2(int[][] A) {
int n = A.length;
int[] v = new int[n];
int somma = 0;
for (int i = 0; i < n; i++)
v[i] = A[i][i];
for (int i = 0; i < n; i++)
somma += v[i];
return somma;
}
public static int sommaDiagonale3(int[][] A) {
int n = A.length;
int somma = 0;
for (int i = 0; i < n; i++)
somma += A[i][i];
return somma;
}

[apatriarca]

Non hai nessuna idea? Sono codici abbastanza standard con solo dei cicli da considerare. Per esempio il primo è \(O(n^2)\) perché visita l'intera matrice in quei due cicli annidati.

[Fab996]

Sisi, avevo delle idee solo non ci sono i risultati e volevo sapere confrontandomi se avevo fatto bene!

[Fab996]

"apatriarca":Non hai nessuna idea? Sono codici abbastanza standard con solo dei cicli da considerare. Per esempio il primo è \(O(n^2)\) perché visita l'intera matrice in quei due cicli annidati.

Gli altri due dovrebbero essere entrambi $O(n)$ ?

[apatriarca]

Sì, esatto.