+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 5 su 5

Discussione: Insertion sort nel merge sort

  1. #1
    SweetDream non è in linea Novello
    Post
    3

    Insertion sort nel merge sort

    Salve, sono un nuovo utente del forum

    un problema del mio libro propone di usare l'insertion sort all'interno del merge sort nel momento in cui i sottoproblemi diventano sufficientemente piccoli, questo per sfruttare i fattori costanti minori della complessità dell'insertion sort.

    Dice: "Si consideri una modifica del merge sort in cui n/k sottoarray di lunghezza k sono ordinati usando l'insertion sort e sono poi combinati usando il meccanismo standard di fusione, con k che deve essere determinato."

    I quesiti sono:

    1- mostrare che i n/k sottoarray, ciascuno di lunghezza k, nel caso peggiore possono essere ordinati dall'insertion sort con un tempo theta(nk)

    Soluzione (mia)

    L'insertion sort ordina un array di k elementi in theta(k^2) nel caso peggiore. Essendo gli array da ordinare n/k si ottiene che il tempo totale nel caso peggiore è theta(n/k * k^2) = theta(nk)

    2- mostrare che i n/k sottoarray possono essere fusi in tempo theta(n*lg(n/k)) sempre considerando il caso peggiore

    Soluzione (mia, con qualche dubbio)

    Costruendo l'albero delle fusioni, ponendo i n/k sottoarray come foglie e l'array intero come radice, la somma di tutte le fusioni che avvengono per ogni livello richiede un tempo pari a theta(n).

    Per la precisione, (assumento che la radice sia al livello 0)
    al livello 1 vengono fusi 2 sottoarray di n/2 elementi => theta(n/2) * 2 = theta(n)
    al livello 2 vengono fusi 4 sottoarray di n/4 elementi => theta(n/4) * 4 = theta(n)
    ...
    al livello log{2}(n/k) vengono fusi n/k sottoarray di k elementi => theta(k) * n/k = theta(n)

    La complessità totale è quindi theta(n) * log{2}(n/k) = theta(n * lg(n/k))

    3- Dato che l'algoritmo modificato viene eseguito, nel caso peggiore, in un tempo theta(nk + n * lg(n/k)) qual è il valore asintotico più grande tale per cui l'algoritmo modificato ha lo stesso tempo di esecuzione del merge sort standard?

    Soluzione (non riesco a trovarla)

    Quello che cerco un valore di k in funzione di n tale che soddisfi

    nk + n * lg(n/k) = n * lg(n)

    che semplificando diventando

    k - lg(k) = 0

    e dato che la funzione logaritmo è sempre al di sotto della bisettrice direi che non esiste nessun k che soddisfa l'equazione.

    non so cosa sbaglio ma mi risulta che nessun k soddisfa l'equazione ma questo significherebbe che l'esercizio non ha molto senso



    Spero possiate aiutarmi, grazie

  2. #2
    Luogo
    Granducato di Toscana
    Post
    836
    Blogs
    40
    Il "tuo" libro (che poi è il CLRS, una Bibbia dell'algoritmica...) pone molti problemi interessanti e spunti di riflessione.

    Riguardo al punto 3, l'unico davvero interessante, occorre solo soffermarsi un attimo ad osservare l'equazione prima di fare dei conti più o meno validi.

    Formula LaTeX: \Theta\left(n\cdot k + n\cdot log_2\frac{n}{k}\right) = \Theta(n\cdot log_2n)

    Se k crescesse più rapidamente di lg(n), il termine Formula LaTeX: \Theta(n\cdot k) porterebbe inevitabilmente a superare Formula LaTeX: \Theta(n\cdot log_2n).

    Dunque è fondamentale assumere che sia:
    Formula LaTeX: k \leq \Theta(log_2n)
    e procedere di conseguenza.

    Se ipotizziamo valida la parte equazionale della relazione d'ordine debole appena scritta, partendo dall'ovvia espressione fornita dal testo del problema, abbiamo facilmente:

    Formula LaTeX: \begin{align*} k = \Theta(log_2n) &\Rightarrow \\\Theta\left(n\cdot k + n\cdot log_2\frac{n}{k}\right) &= \Theta\left(n\cdot log_2n + n\cdot log_2\frac{n}{log_2n}\right)\\&= \Theta \left(n\cdot log_2n + n\cdot log_2n - n\cdot log_2\left(log_2n\right)\right)\\&= \Theta(n\cdot log_2n)\end{align*}

    In sostanza, quel valore di k "risolve l'equazione" dal punto di vista algebrico: si ottiene di fatto la medesima complessità asintotica dell'algoritmo originale. Ciò risponde alla richiesta dell'esercizio.
    Almeno in teoria: in pratica, nei laboratori didattici, il valore di k è determinato sperimentalmente come il break-even point delle misure di profiling puntuale tra le specifiche implementazioni dei due distinti algoritmi, e viene quindi a coincidere con la dimensione effettiva dell'intput massimo per il quale l'insertion sort supera in prestazioni il mergesort.
    Ultima modifica di M.A.W. 1968; 29-01-2014 02:33  Motivo: Capriccio dell'interprete Latex
    Tutti gli utenti sono pregati di prendere visione del Regolamento del Forum e di rispettarlo.

    Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo... già che ci siete, leggete questa selezione di parole famose di alcuni tra i più grandi geni.

    • Un plauso a Grisha Perelman, raro esempio di genuino anticonformismo umano e scientifico.

  3. #3
    SweetDream non è in linea Novello
    Post
    3
    Grazie sei stato molto chiaro.

    Quindi l'errore che commettevo era cercare una funzione k ben precisa che soddisfasse l'equazione su tutti i valori di n e non tenevo conto che in realtà era sufficiente trovare un insieme di funzioni che asintoticamente davano all'algoritmo in questione la stessa complessità del merge sort?

  4. #4
    Luogo
    Granducato di Toscana
    Post
    836
    Blogs
    40
    L'errore consiste nel tentare di risolvere algebricamente l'equazione come se fosse una qualsiasi uguaglianza, trascurando l'operatore teta. Se è vero che in molti casi ciò risulta ugualmente possibile, e che in (troppi) corsi di complessità computazionale il rigore formale è un optional, è anche vero che in un caso come questo doveva metterti immediatamente in allarme la "scomparsa" algebrica di n (per la legge di annullamento del prodotto), laddove il testo richiedeva esplicitamente una soluzione per k in funzione di n.

    Portando il ragionamento al passo successivo, nelle logiche equazionali e in molte algebre superiori le regolette dell'algebra di Al Kwarizmi non valgono più (non tutte), e si deve lavorare separatamente sui due membri equazionali, cercando di riportarli alla medesima forma. Spesso è così anche con gli operatori delle notazioni asintotiche, con molti tipi di trasformate, e con vari altri oggetti matematici. Consiglio anzi, per il prosieguo degli studi, uno dei rarissimi (se non unico) testi in italiano che tratta metodi matematici avanzati in complessità computazionale, corredato anche di una buona bibliografia che contiene praticamente tutti gli altri riferimenti più validi nella letteratura in lingua inglese.
    Ultima modifica di M.A.W. 1968; 29-01-2014 16:47 
    Tutti gli utenti sono pregati di prendere visione del Regolamento del Forum e di rispettarlo.

    Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo... già che ci siete, leggete questa selezione di parole famose di alcuni tra i più grandi geni.

    • Un plauso a Grisha Perelman, raro esempio di genuino anticonformismo umano e scientifico.

  5. #5
    SweetDream non è in linea Novello
    Post
    3
    Grazie, adesso che lo so starò più attento in futuro e comprerò quel libro

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi