[Java] Costo computazionale algoritmi.

[dexter86]

Salve, sono alle prese con questo esame e ho qualche difficoltà nel calcolo dei costi computazionali degli algoritmi.


Si considerino i seguenti metodi:

public static int metodo3(int n) {
    return metodo2(metodo1(n));
}

public static int metodo2(int[] a) {
    for (int i=0; i<=a.length / 2; i++) {
        for (int j=i; j<a.length; j++) {
            if (a[j] < a[i]) {
                int aux = a[j];
                a[j] = a[i];
                a[i] = aux;
            }
        }
    }
    return a[a.length/2];
}

public static int[] metodo1(int n) {
    LinkedList<Integer> in = new LinkedList<Integer>();
    while (n>0) {
        in.add(n % 10); //resto della divisione intera
        n = n / 10;
    }
    
    Iterator<Integer> iterator = in.iterator();
    int i = 0;
    int[] val = new int[in.size()];
    while (iterator.hasNext()) {
        val[in.size() - i - 1] = iterator.next();
        i++;
    }
    return val;
}

Si richiede quanto segue:
1. Determinare il costo computazionale di metodo1 in funzione del valore n e in funzione della dimensione dell'input.
2. Determinare il costo computazionale di metodo2 in funzione del valore n e in funzione della dimensione dell'input.
3. Determinare il costo computazionale di metodo3 in funzione del valore n e in funzione della dimensione dell'input.

Qualcuno saprebbe aiutarmi? Grazie mille

[LeleFT]

Originariamente inviato da dexter86
Qualcuno saprebbe aiutarmi? Grazie mille

Prima proponi le tue soluzioni, spiegando anche come sei arrivato a quelle conclusioni. Su quelle si discute.


Ciao.

[newhook]

forse:
1 O(n)
2 O(n^2)
3 = 2

che dici? secondo te?

[desa]

Ad occhio mi sembrano ragionevoli...

[donato.sciarra]

concordo

[dexter86]

Grazie per le risposte.

Io avrei detto:

Metodo 1 - l'operazione dominante è il ciclo while(n>0), e dato che il numero n viene diviso ad ogni iterazione per 10, il numero di iterazioni per arrivare a zero è Log(n).
Quindi metodo1 ha costo in termini di tempo O(Log(n)) (con Log(n) intendo il logaritmo in base 10)

...in funzione della dimensione dell'input, ovvero del numero di bit che serve per rappresentare l'intero n.

Tale numero è x=O[ln(n)] ---> n=O[2^x]

e quindi basta sostituire... ----> il costo in funzione della dim. dell'input è O[Log(2^x)]


Metodo2 - direi anch'io che ha costo quadratico

su metodo3, ho qualche perplessità, direi che ha un costo che è la somma di metodo1 e metodo2 (ma non ne sono sicurissimo)