Aiuto complessità in passi base/complessità asintotica

di il
8 risposte

Aiuto complessità in passi base/complessità asintotica

Salve, sono uno studente di ingegneria e a breve dovrò sostenere l'esame di informatica sul linguaggio di programmazione Java.
Nei compiti d'esame è sempre presente un esercizio sul calcolo della complessità in passi base e complessità asintotica (come nell'immagine).
Avendo saltato la lezione sulla spiegazione della complessità sono proprio in alto mare, anche dalle slide del professore non ho capito un granché, qualcuno mi spiegherebbe in termini semplici e con esempi come posso risolvere questa tipologia di esercizi? Grazie mille!

8 Risposte

  • Re: Aiuto complessità in passi base/complessità asintotica

    Caspita una sola lezione per quello che normalmente è un intero corso? Quali sono i tuoi dubbi?
  • Re: Aiuto complessità in passi base/complessità asintotica

    Ciao, praticamente ho saltato una settimana ma probabilmente non ci sarà stata spiegata in maniera approfondita come dici tu la complessità, anche perché il corso è principalmente sulla programmazione in Java.
    Se riesci a illustrarmi come si risolve l'esercizio nell'immagine sopra saresti già di grandissimo aiuto anche perché è una tipologia di esercizio standard che c'è sempre all'esame. Grazie
  • Re: Aiuto complessità in passi base/complessità asintotica

    .
  • Re: Aiuto complessità in passi base/complessità asintotica

    Grazie mille per la totale spiegazione però, ancora, credo sia più semplice di quello che hai scritto. Per esempio questa è la soluzione dell'esercizio:

    Vorrei solo capire/sapere PERCHE' vengono quei numeri per riuscire a farlo da solo. Grazie ancora.
  • Re: Aiuto complessità in passi base/complessità asintotica

    Bhè come avevo intuito è a livello principiante.
    La risposta è: banalmente controlla i costrutti iterativi, ovvero cicli FOR e WHILE (o quello che è).
    Se hai solo cicli FOR puoi calcolare esattamente quante operazioni fai.

    Esempio scemissimo
    for i=1 to N
       totale = totale +i
    
    In questo caso sai di fare esattamente 2N operazioni (in realtà ne fai 4N, perchè hai un test e un jump, e in realtà ne fai anche di più, ma sei a livello-base, non complichiamo la vita), che sono
    - un assegnamento
    - una somma
    Quindi se N è 10, farai 10 somme e 10 assegnamenti.
    la complessità è ovviamente o(N), o anche (meglio) 2N.
    Non hai casi peggiori: il ciclo è sempre quello, quindi sempre tot è il tempo.

    Se invece hai cose "strane", tipo
    
      while qualcosa > qualcosa
          ... boh...
    
    allora devi considerare che il ciclo può essere eseguito
    -mai (complessità 0)
    -una volta
    -tante volte
    - un numero variabile di volte, a seconda dei casi.

    Ecco quindi che devi indicare sia la complessità PEGGIORE, cioè quando sei proprio sfortunato ed ogni singolo test "va male".
    Poi si studia normalmente quella MEDIA (ma penso sia troppo difficile per te, ci vuole calcolo della probabilità, non credo si insegni a ingegneria, potrei sbagliare).

    Vado a pranzo, ciao.

    PS ovviamente do per scontato che nessuno ti abbia spiegato il calcolo "effettivo" della complessità, dove c'è il doppio problema dell'asintotica, e dei moltiplicatori (cioè i coefficienti) e infine dell'implementazione effettiva.
    Paradossalmente, infatti, non tutte le operazioni elementari hanno lo stesso costo (cioè vengono tradotti in istruzioni-macchina più o meno veloci).
    Non è immediato stabilire se è meglio un algoritmo che fa 10N(moltiplicazioni)+10000(assegnamenti) vs 3000N (assegnamenti) vs 10N(moltiplicazioni) + 200N (assegnamenti).

    Ancor meno è facile capire se è sempre meglio o(n^2) invece di o(n^3) [sottolineo sempre]

    Son tutte cose molto, ma molto complicate, se affrontate rigorosamente e non spannometricamente.
    Fortunatamente per te, sicuro al 100% per la spannometria
  • Re: Aiuto complessità in passi base/complessità asintotica

    Grazie ancora, però se non ti dispiace riusciresti ad illustrarmi nel caso dell'esercizio sopra perché lo ha risolto in quel modo? Spiegando ogni passaggio se puoi.
  • Re: Aiuto complessità in passi base/complessità asintotica

    È già spiegato passo per passo, cosa non è chiaro?
    la funzione f (in realtà manca il discorso del passaggio parametri, stack e così via, quindi siamo nella versione didattica) ha 3 righe
    - nella prima inizializzi le variabili (2 assegnamenti)
    - nella seconda hai un ciclo while che viene ripetuto ~N/2 volte (perchè? perchè i viene incrementato DUE volte)
    - nella terza fa una somma N/2 volte
    quindi vedi la complessità della funzione f sommando i vari passi.
    A "occhio" avresti già potuto vedere che, essendo il ciclo eseguito o(N) volte, la complessità sarà a sua volta o(N)

    la seconda parte te la lascio per esercizio
    A "occhio" sempre avresti visto che viene eseguito il ciclo di g o(N), pertanto la complessità complessiva è data da un doppio ciclo annidato, cioè o(N*N) => o(N^2).

    Questo, in pratica, è il risultato che ti aspetti (guardando l'esercizio, senza far nessun conto, in 3 secondi arrivi al risultato).
    Ora ti metti con calma e sangue freddo a calcolare tutte le volte che i vari cicli vengono eseguiti, poi li sommi tutti, e alla fine devi ottenere un polinomio di secondo grado (con coefficienti diversi).

    Se, facendo i conti, ti venisse che so o(N^3) allora sapresti già di aver sbagliato.
  • Re: Aiuto complessità in passi base/complessità asintotica

    Grazie mille sei stato davvero di grande aiuto!
Devi accedere o registrarti per scrivere nel forum
8 risposte