Lower bound temporale: (n)



Scaricare 470 Kb.
Pagina1/5
23.03.2019
Dimensione del file470 Kb.
  1   2   3   4   5





Lower bound temporale: (n)

  • Lower bound temporale: (n)

    • “banale”: dimensione dell’input
  • Upper bound temporale: O(n2)

    • Insertion Sort 2 e 3




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

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

  • Un generico algoritmo di ordinamento per confronti lavora nel modo seguente:

    • Confronta due elementi ai ed aj (ad esempio effettua il test ai  aj);
    • A seconda del risultato, riordina e/o decide il confronto successivo da eseguire.
  •  Un algoritmo di ordinamento per confronti può essere descritto in modo astratto usando un albero di decisione, nel quale i nodi interni rappresentano i confronti, mentre le foglie rappresentano gli output prodotti






Condividi con i tuoi amici:
  1   2   3   4   5


©astratto.info 2019
invia messaggio

    Pagina principale