Complessità

di il
11 risposte

Complessità

Ciao a tutti, sono nuovo del forum, studio ingegneria e attualmente sono alle prese con l'esame di tecniche di programmazione che utilizza Java come linguaggio.
A livello di codice diciamo che riesco a cavarmela discretamente il mio problema più grande è la complessità. Cerco di spiegarmi, in genarale ho capito il concetto e guardando in giro sul web ho trovato anche come calcolarla partendo dai passi base e poi i vari operatori asintotici. Il problema nasce nel momento in cui vado ad usare metodi propri del linguaggio Java. Come faccio a calcolare la complessità nel momento in cui utilizzo classi come LinkedList ecc..Come devo muovermi? avete qualche link, sito o guida che mi possa aiutari con esempi?
Grazie

11 Risposte

  • Re: Complessità

    Non complicarti la vita.

    Quando usi una struttura dati in Java, cerca l'equivalente modello teorico.

    Non ti interessa l'implementazione nei dettagli, ma solo quella generale.

    Una LinkedList Java e' una lista fatta di nodi, quindi: scansione O(N), aggiunta o rimozione in testa ed in coda O(1), rimozione in mezzo O(N)

    Una HashMap usa una tabella hash, un TreeMap usa un albero, ecc.
  • Re: Complessità

    Ma ha senso imparare cammini minimi alberi grafi kruskal dijkstra, c'è da uscire pazzi per un solo esame se però sono cose che mi possono servire faccio lo sforzo..
    Perché comunque il codice da scrivere all'esame non è molto complicato anzi..
  • Re: Complessità

    Ma che domande fai!

    DIPENDE!

    Se vai a fare l'HTML-ista, probabilmente no.

    Se vai a implementare algoritmi per l'acquisizione dei dati dai contatori, IN TEMPO REALE, sulla rete elettrica presso l'Enel (30.000.000 di contatori!!!), molto probabilmente si.
  • Re: Complessità

    Bene, la risposta nel mio caso è no. Ti ringrazio
  • Re: Complessità

    Ipotizzando di avere una lista e un metodo get che mi restituisce questa lista, la complessità quale sarà?
    l'istruzione va considerata come una passo base con costo 1? oppure il metodo ritorna tutti gli elementi della lista e quindi il costo sarà lineare O(n)?
  • Re: Complessità

    Drenthe24 ha scritto:


    Ipotizzando di avere una lista e un metodo get che mi restituisce questa lista, la complessità quale sarà?
    Se un metodo restituisce semplicemente un valore o un reference (es. ad una lista), allora non si parla (normalmente) nemmeno di complessità.
    Il concetto di complessità entra in gioco quando c'è un "algoritmo" la cui complessità dipende e varia, più o meno, proporzionalmente al numero di elementi da gestire, generare, elaborare, iterare, ecc...
  • Re: Complessità

    Ok capito mi sembrava che nel caso della lista ci fosse un algoritmo dietro per questo chiedevo.Grazie mille
  • Re: Complessità

    Drenthe24 ha scritto:


    Ok capito mi sembrava che nel caso della lista ci fosse un algoritmo dietro per questo chiedevo.Grazie mille
    Alt, l'ho detto prima (anche se dovevo essere più preciso): un conto è un metodo che restituisce direttamente un valore, una variabile.
    public class Persona {
        private String nome;
    
        public String getNome() {
            return nome;
        }
    }
    Il getNome non si dice (normalmente) che ha una qualche complessità. Non c'entra molto qui. E' talmente trascurabile ...

    Un altro conto è il get(int index) di un java.util.List.
    Il get(int index) di ArrayList ha complessità O(1) ovvero "tempo costante". Non c'è differenza tra fare l.get(0) e l.get(1000000) (ammesso di avere tali indici).
    Il get(int index) di LinkedList ha complessità O(N) ovvero dipende dall'indice. Ma questo perché dietro il get di LinkedList c'è proprio un "algoritmo" che è più complesso che restituire una variabile: deve scansionare una lista linkata, nodo per nodo.

    Quindi la questione è ovviamente COSA fa il metodo!
  • Re: Complessità

    Io intendo proprio un comando che mi restituisce l'intera lista.
    es. un metodo che come corpo ha solo un return list(di tipo linked list) in questo caso cosa viene passato? un indirizzo? Non so se sono stato chiarissimo, scusatemi.
    mettiamo il caso che io dichiari una lista private e poi voglio un metodo get pubblico che mi restituisce questa lista..cosa mi viene passato un indirizzo? O(1)?
  • Re: Complessità

    Drenthe24 ha scritto:


    Io intendo proprio un comando che mi restituisce l'intera lista.
    public class ListaContatti {
        private List<Persona> listaPersone = new LinkedList<Persona>();
    
        // .....
    
        public List<Persona> getPersone() {
            return listaPersone;
        }
    }
    Il getPersone() restituisce semplicemente un reference, che alla fin fine è un valore che per la JVM denota in un qualche modo (specifico della JVM e anche in base al S.O.) un "indirizzo" all'oggetto della lista. E pertanto la "complessità" del getPersone() è assolutamente TRASCURABILE.

    Se proprio devi tirar fuori la indicazione della complessità (per qualche oscuro motivo "didattico" per cui ti impongono di spaccare il capello in due per fare chissà quali elucubrazioni accademiche ..), potresti indicare O(1) ma all'atto pratico e nella programmazione Java in generale, un getter di quel tipo non gliene frega niente a nessuno della "complessità".
  • Re: Complessità

    Grazie mille ora ho capito tutto
Devi accedere o registrarti per scrivere nel forum
11 risposte