[Risolto][Python] Complessità degli algoritmi

Linguaggi di programmazione: php, perl, python, C, bash, ecc.

[Risolto][Python] Complessità degli algoritmi

Messaggioda Gianluca912 » sabato 15 luglio 2017, 12:37

Salve, come da titolo volevo delle informazioni riguardanti la complessità degli algoritmi, nel titolo ho inserito [Python] perché porto degli esempi in questo linguaggio. Dunque:
Per calcolare il fattoriale di un numero si può usare questa funzione:
Codice: Seleziona tutto
def fattoriale(n):
        if n==0:
            return 1
        return n*fattoriale(n-1)

la cui complessità computazionale si può definire lineare mentre l'ordine di crescita è fattoriale cioè più che esponenziale.
Adesso invece pongo i quesiti, questa funzione converte un numero in una stringa '0-1' corrispondente al valore binario del numero passato, anch'essa è ricorsiva:
Codice: Seleziona tutto
def convBin(n):
        if n==0:
            return ' '
        return convBin(n//2)+str(n%2)

di questa funzione non sono certo di quale sia la complessità computazionale, secondo me potrebbe essere logaritmica, mentre mi domando con ancora più dubbi questa funzione ha un ordine di crescita?
(Con ordine di crescita intendo ad esempio: lineare, quadratica, cubica, esponenziale, logaritmica ecc..)
La seconda funzione serve per calcolare il binomiale chiaramente scritta in forma ricorsiva è meno efficiente rispetto a quella iterativa che fa uso della formula: [n!/k!*(n-k)!] in termini di tempi di risoluzione, comunque:
Codice: Seleziona tutto
def coefBin(n,k):
      if k==0 or k==n:
          return 1
      return coefBin(n-1,k-1) + coefBin(n-1,k)

Mi domando, è corretto dire che la complessità computazionale è esponenziale e l'ordine di crescita è esponenziale?

Aggiungo ulteriori domande:
Come fate voi a determinare la complessità di risoluzione e l'ordine di crescita di una funzione ricorsiva? (di quelle iterative basta guardare le singole istruzioni e i costrutti come while, for ecc.. giusto?)
Potreste farmi qualche esempio di funzione ricorsiva con ordine di crescita quadratica o cubica, e anche qualcuna con complessità quadratica e/o cubica?
Grazie.
Ultima modifica di Gianluca912 il lunedì 17 luglio 2017, 21:51, modificato 1 volta in totale.
Hello :)
Gianluca912
Prode Principiante
 
Messaggi: 62
Iscrizione: dicembre 2012
Desktop: Explorer
Distribuzione: Windows 10 Pro (x64)
Sesso: Maschile

Re: [Python] Complessità degli algoritmi

Messaggioda melfnt » sabato 15 luglio 2017, 18:29

Ciao!
Di solito la complessità di un algoritmo si calcola in funzione della dimensione dell'input.

Gianluca912 Immagine ha scritto:Salve, come da titolo volevo delle informazioni riguardanti la complessità degli algoritmi, nel titolo ho inserito [Python] perché porto degli esempi in questo linguaggio. Dunque:
Per calcolare il fattoriale di un numero si può usare questa funzione:
Codice: Seleziona tutto
def fattoriale(n):
        if n==0:
            return 1
        return n*fattoriale(n-1)

la cui complessità computazionale si può definire lineare mentre l'ordine di crescita è fattoriale cioè più che esponenziale.



Quasi. Questa funzione è lineare in n (perché impiega esattamente n passi per terminare) però è esponenziale nella taglia dell'input, che è log n.
La faccenda è un po' complicata e non intuitiva, per schiarirti le idee ti consiglio di rifletterci molto su e di leggere questo.

Adesso invece pongo i quesiti, questa funzione converte un numero in una stringa '0-1' corrispondente al valore binario del numero passato, anch'essa è ricorsiva:
Codice: Seleziona tutto
def convBin(n):
        if n==0:
            return ' '
        return convBin(n//2)+str(n%2)

di questa funzione non sono certo di quale sia la complessità computazionale, secondo me potrebbe essere logaritmica, mentre mi domando con ancora più dubbi questa funzione ha un ordine di crescita?
(Con ordine di crescita intendo ad esempio: lineare, quadratica, cubica, esponenziale, logaritmica ecc..)


Sempre logaritmica in n, (impiega log n passi) ma lineare nella dimensione dell'input.

La seconda funzione serve per calcolare il binomiale chiaramente scritta in forma ricorsiva è meno efficiente rispetto a quella iterativa che fa uso della formula: [n!/k!*(n-k)!] in termini di tempi di risoluzione, comunque:
Codice: Seleziona tutto
def coefBin(n,k):
      if k==0 or k==n:
          return 1
      return coefBin(n-1,k-1) + coefBin(n-1,k)

Mi domando, è corretto dire che la complessità computazionale è esponenziale e l'ordine di crescita è esponenziale?


Per calcolare la complessità di questa funzione serve una dimostrazione ad hoc oppure strumenti di analisi della complessità più avanzati, come il master theorem a due variabili, che purtroppo non so applicare.

Aggiungo ulteriori domande:
Come fate voi a determinare la complessità di risoluzione e l'ordine di crescita di una funzione ricorsiva? (di quelle iterative basta guardare le singole istruzioni e i costrutti come while, for ecc.. giusto?)
Potreste farmi qualche esempio di funzione ricorsiva con ordine di crescita quadratica o cubica, e anche qualcuna con complessità quadratica e/o cubica?
Grazie.


Innanzitutto d'ora in poi ti consiglio di lavorare con liste di n elementi in input e di calcolare la complessità in funzione di n, invece che con un solo intero.
Lineare:
Codice: Seleziona tutto
def somma (L):
    if len(L)==0:
        return 0
    return L[0] + somma (L[:1])

Quanti passi impiega questa funzione su una lista di n elementi?

Quadratica:
Codice: Seleziona tutto
def tutte_le_coppie (x, L):
    if len(L) == 0:
        return []
    return [ (x,L[0]) ] + tutte_le_coppie (x, L[1:] )

def combinazioni (L):
    if len(L)==0:
        return []
    return tutte_le_coppie (L[0], L[1:]) + combinazioni (L[1:])

Quanti passi impiega la funzione combinazioni su una lista di n elementi?

Cubica
Codice: Seleziona tutto
def concatena_combinazioni (L):
    if len(L) == 0:
        return []
    return combinazioni (L) + concatena_combinazioni (L[1:])

Quanti passi impiega la funzione concatena_combinazioni su una lista di n elementi?

(;
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1184
Iscrizione: ottobre 2011

Re: [Python] Complessità degli algoritmi

Messaggioda melfnt » domenica 16 luglio 2017, 10:40

melfnt Immagine ha scritto:
La seconda funzione serve per calcolare il binomiale chiaramente scritta in forma ricorsiva è meno efficiente rispetto a quella iterativa che fa uso della formula: [n!/k!*(n-k)!] in termini di tempi di risoluzione, comunque:
Codice: Seleziona tutto
def coefBin(n,k):
      if k==0 or k==n:
          return 1
      return coefBin(n-1,k-1) + coefBin(n-1,k)

Mi domando, è corretto dire che la complessità computazionale è esponenziale e l'ordine di crescita è esponenziale?


Per calcolare la complessità di questa funzione serve una dimostrazione ad hoc oppure strumenti di analisi della complessità più avanzati, come il master theorem a due variabili, che purtroppo non so applicare.



Nel frattempo ho trovato una sorta di dimostrazione ad hoc per provare che la complessità di questa funzione è almeno esponenziale in n.
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1184
Iscrizione: ottobre 2011

Re: [Python] Complessità degli algoritmi

Messaggioda Gianluca912 » domenica 16 luglio 2017, 15:37

Grazie mille melfnt del chiarimento, mi è stata di grande aiuto anche la dimostrazione del binomiale, l'unica cosa che non capisco è cosa cambia nell'usare un oggetto lista o una variabile n, è vero che gli esempi che ho portato io usavano in input solo variabili semplici, ma anche con l'uso delle liste il calcolo della complessità si fa allo stesso modo, per esempio la funzione somma che hai scritto ricorsiva iterativa sarebbe:
Codice: Seleziona tutto
def somma(L):
        sum=0
        for i in range(0,len(L)):
                sum += L[i]
         return sum

la cui complessità è comunque lineare, certo passando solo due elementi alla funzione (e non una lista) la complessità sarebbe costante, non essendoci n elementi da scorrere. Quindi che io effettui delle prove con l'uso di liste o con l'uso di singole variabili, il risultato è equivalente, alla fine ciò che cambia è il fatto che devo tenere in considerazione la presenza di più elementi in input, no?
Infatti come hai detto tu la complessità di un algoritmo si calcola in base alla dimensione dell'input. Anche se una definizione più appropriata potrebbe essere:
"la complessità di un algoritmo è la funzione che associa alla dimensione del problema (legata al numero di dati in input), il costo della sua risoluzione in base alla misura scelta"

Tornando un attimo sulla funzione che calcola il fattoriale di n, mi torna il fatto che siano necessari n passi per far terminare la funzione, ma non capisco perché sarebbe esponenziale nella taglia dell'input se ciò che passo è solamente n (sempre che abbia compreso cosa s'intende con taglia dell'input ), sinceramente con ordine di crescita io intendevo, l'output della funzione all'incrementare di n, il quale è fattoriale e non esponenziale (testata con geogebra), e non log n.

Per rispondere alle tue domande (sempre che io abbia capito cosa siano i passi):
direi che somma(L) impiega 1*n passi base
mentre combinazioni impiega 1+1*n*n passi base
invece l'ultima impiega 1+1+1*n*n*n passi base
quindi le mie risposte sono corrette? (Come passo base si considera anche la condizione?)
Hello :)
Gianluca912
Prode Principiante
 
Messaggi: 62
Iscrizione: dicembre 2012
Desktop: Explorer
Distribuzione: Windows 10 Pro (x64)
Sesso: Maschile

Re: [Python] Complessità degli algoritmi

Messaggioda melfnt » domenica 16 luglio 2017, 20:12

Gianluca912 Immagine ha scritto:Grazie mille melfnt del chiarimento, mi è stata di grande aiuto anche la dimostrazione del binomiale, l'unica cosa che non capisco è cosa cambia nell'usare un oggetto lista o una variabile n, è vero che gli esempi che ho portato io usavano in input solo variabili semplici, ma anche con l'uso delle liste il calcolo della complessità si fa allo stesso modo, per esempio la funzione somma che hai scritto ricorsiva iterativa sarebbe:
Codice: Seleziona tutto
def somma(L):
        sum=0
        for i in range(0,len(L)):
                sum += L[i]
         return sum

la cui complessità è comunque lineare, certo passando solo due elementi alla funzione (e non una lista) la complessità sarebbe costante, non essendoci n elementi da scorrere. Quindi che io effettui delle prove con l'uso di liste o con l'uso di singole variabili, il risultato è equivalente, alla fine ciò che cambia è il fatto che devo tenere in considerazione la presenza di più elementi in input, no?
Infatti come hai detto tu la complessità di un algoritmo si calcola in base alla dimensione dell'input. Anche se una definizione più appropriata potrebbe essere:
"la complessità di un algoritmo è la funzione che associa alla dimensione del problema (legata al numero di dati in input), il costo della sua risoluzione in base alla misura scelta"

Tornando un attimo sulla funzione che calcola il fattoriale di n, mi torna il fatto che siano necessari n passi per far terminare la funzione, ma non capisco perché sarebbe esponenziale nella taglia dell'input se ciò che passo è solamente n (sempre che abbia compreso cosa s'intende con taglia dell'input ), sinceramente con ordine di crescita io intendevo, l'output della funzione all'incrementare di n, il quale è fattoriale e non esponenziale (testata con geogebra), e non log n.


La funzione fattoriale riceve come input un solo intero, ma la sua complessità è O(n). Confrontala un attimo con la funzione somma, che riceve in input una *lista di n elementi* e ha complessità n. Non sono la stessa cosa, vero?
La funzione somma esegue un numero di passi pari alla dimensione dell'input (e quindi si dice che ha complessità lineare).
La funzione fattoriale, invece, esegue n passi, mentre l'input ha dimensione log n (questo è infatti il numero di cifre necessarie per rappresentare n).

In altre parole: facciamo sì che l'input di fattoriale sia effettivamente lungo n. Quindi diciamo che fattoriale (N) prende in input un numero N (maiuscolo) che ha dimensione n. Prova a rispondere a queste domande:
1) quanto vale N in funzione di n?
2) quanti passi impiega la funzione fattoriale (N) a terminare?
2) quanto è la sua complessità in funzione della taglia dell'input (ovvero in funzione di n)?

Questo ti dovrebbe far capire la differenza fra le funzioni che hanno in input un numero n e quelle che hanno in input n numeri.

Per quanto riguarda infine l'ordine di crescita delle funzioni, dipende dal risultato restituito dalle funzioni: spesso è legato alla complessità, ma non sempre.
Ciò significa che potrebbero esserci funzioni (matematiche) con ordine di crescita grande, ma che sono facili da calcolare, e viceversa. Vedi se riesci a trovare degli esempi.
Le funzioni con liste come parametri non hanno ordine di crescita.

Per rispondere alle tue domande (sempre che io abbia capito cosa siano i passi):
direi che somma(L) impiega 1*n passi base
mentre combinazioni impiega 1+1*n*n passi base
invece l'ultima impiega 1+1+1*n*n*n passi base
quindi le mie risposte sono corrette? (Come passo base si considera anche la condizione?)


tre risposte esatte.
In particolare, sono tre funzioni ricorsive, la prima ha complessità lineare, la seconda quadratica (esegue n^2 passi) e l'ultima cubica (esegue circa n^3 passi). Quindi sono le funzioni da te richieste: ricorsive e con complessità più che lineari.

Alcuni termini dell'equazione del calcolo della complessità di solito non si considerano: si conta solo quello che cresce più velocemente al crescere di n (che è anche quello con ordine di crescita più grande). Questo perché molto spesso si interessati solo alla complessità asintotica degli algoritmi.

Quindi per esempio, anche una funzione che impiega 4n^3 + 12n^2 + 150 passi per terminare ha complessità cubica.
Per approfondire leggi questo.
(;
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1184
Iscrizione: ottobre 2011

Re: [Python] Complessità degli algoritmi

Messaggioda Gianluca912 » lunedì 17 luglio 2017, 21:50

Grazie ancora della risposta tempestiva, chiara e completa. Credo che le risposte siano:
1) N ha dimensione n
2) fattoriale di n impiega n passi a terminare
3) la complessità in taglia dell'input di fattoriale(n) è log(n)
Direi di poter mettere [RISOLTO], anche se su questo argomento ho ancora molto da imparare. Grazie.
Hello :)
Gianluca912
Prode Principiante
 
Messaggi: 62
Iscrizione: dicembre 2012
Desktop: Explorer
Distribuzione: Windows 10 Pro (x64)
Sesso: Maschile

Re: [Python] Complessità degli algoritmi

Messaggioda melfnt » martedì 18 luglio 2017, 10:57

Gianluca912 Immagine ha scritto:Grazie ancora della risposta tempestiva, chiara e completa. Credo che le risposte siano:
1) N ha dimensione n


Sì, è vero: N ha dimensione n. Ma qual'è il suo *valore* in funzione di n? Il valore, non la dimensione occupata.

2) fattoriale di n impiega n passi a terminare


Sì, e quindi fattoriale di N, ne impiega N (maiuscolo).

3) la complessità in taglia dell'input di fattoriale(n) è log(n)


Perché log(n)? Devi scrivere il numero di passi impiegati (N) in funzione della taglia dell'input (n), quella è la complessità dell'algoritmo.
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1184
Iscrizione: ottobre 2011

Re: [Risolto][Python] Complessità degli algoritmi

Messaggioda Gianluca912 » mercoledì 19 luglio 2017, 11:18

Ok, dovrò studiare ancora molto per capire bene questi argomenti.
Hello :)
Gianluca912
Prode Principiante
 
Messaggi: 62
Iscrizione: dicembre 2012
Desktop: Explorer
Distribuzione: Windows 10 Pro (x64)
Sesso: Maschile


Torna a Programmazione

Chi c’è in linea

Visualizzano questa sezione: Yahoo [Bot] e 1 ospite