Algoritmi e Strutture Dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano



Scaricare 464 b.
17.11.2017
Dimensione del file464 b.


Algoritmi e Strutture Dati


Delimitazione inferiore alla quantità di una certa risorsa di calcolo necessaria per risolvere un problema

  • Delimitazione inferiore alla quantità di una certa risorsa di calcolo necessaria per risolvere un problema

  • (n log n) è un lower bound al numero di confronti richiesti per ordinare n oggetti

  • Consideriamo un generico algoritmo A, che ordina eseguendo solo confronti: dimostreremo che A esegue (n log n) confronti



…alcuni richiami…



…per il problema dell’ordinamento…

  • Upper bound: O(n2)

    • Insertio Sort, Selection Sort, Boubble Sort
  • Lower bound: (n)

    • banale: dimensione dell’input






Descrive le diverse sequenze di confronti che A potrebbe fare su istanze di lunghezza n

  • Descrive le diverse sequenze di confronti che A potrebbe fare su istanze di lunghezza n





Per una particolare istanza, i confronti eseguiti da A su quella istanza rappresentano un cammino radice – foglia

  • Per una particolare istanza, i confronti eseguiti da A su quella istanza rappresentano un cammino radice – foglia

  • L’algoritmo segue un cammino diverso a seconda delle caratteristiche dell’input

    • Caso peggiore: cammino più lungo
    • Caso migliore: cammino più breve
  • Il numero di confronti nel caso peggiore è pari all’altezza dell’albero di decisione

  • Un albero di decisione per l’ordinamento di n elementi contiene almeno n! foglie



Un albero binario con k foglie tale che ogni nodo interno ha esattamente due figli ha altezza almeno log2 k

  • Un albero binario con k foglie tale che ogni nodo interno ha esattamente due figli ha altezza almeno log2 k

  • Dimostrazione per induzione su k



L’altezza h dell’albero di decisione è almeno log2 (n!)

  • L’altezza h dell’albero di decisione è almeno log2 (n!)

  • Formula di Stirling: n! (2n)1/2 ·(n/e)n



Esercizio Fornire l’albero di decisione del seguente algoritmo per istanze di dimensione 3.









©astratto.info 2017
invia messaggio

    Pagina principale