 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
esercizio algoritmi
Clicca QUI per vedere il messaggio nel forum |
| mauri |
Ciao a tutti,ho bisogno di una mano.Dopo aver fatto il punto a mi sn trovato in difficoltà sul punto b.
Io penso ke il tempo di calcolo sia:
sommatoria ke va da i=0 a n di 2c.
Dove c identifica il tempo di calcolo delle 2 istruzioni del ciclo.Siccome nn posso avere 1 riscontro chiedo a voi se qst soluzione possa essere giusta.
Qst è il testo dell'esercizio:
Dato un intero n > 2, sia T l’albero di ricerca binaria formato da un solo nodo di etichetta n.
Eseguiamo su T il seguente algoritmo che introduce nuovi nodi nell’albero utilizzando la tradizionale
procedura di inserimento negli alberi di ricerca binaria.
for i = 1, . . . , n − 1 do
begin
inserisci in T un nodo di etichetta i
inserisci in T un nodo di etichetta n + i
end
a) Descrivere l’albero di ricerca binaria prodotto dall’algoritmo.
b) Valutare in funzione di n l’ordine di grandezza del tempo di calcolo richiesto assumendo il
criterio uniforme.
grazie anticipatamente...ciaooo ;););) |
| darkshadow |
Originally posted by mauri
Ciao a tutti,ho bisogno di una mano.Dopo aver fatto il punto a mi sn trovato in difficoltà sul punto b.
Io penso ke il tempo di calcolo sia:
sommatoria ke va da i=0 a n di 2c.
Dove c identifica il tempo di calcolo delle 2 istruzioni del ciclo.Siccome nn posso avere 1 riscontro chiedo a voi se qst soluzione possa essere giusta.
Qst è il testo dell'esercizio:
Dato un intero n > 2, sia T l’albero di ricerca binaria formato da un solo nodo di etichetta n.
Eseguiamo su T il seguente algoritmo che introduce nuovi nodi nell’albero utilizzando la tradizionale
procedura di inserimento negli alberi di ricerca binaria.
for i = 1, . . . , n − 1 do
begin
inserisci in T un nodo di etichetta i
inserisci in T un nodo di etichetta n + i
end
a) Descrivere l’albero di ricerca binaria prodotto dall’algoritmo.
b) Valutare in funzione di n l’ordine di grandezza del tempo di calcolo richiesto assumendo il
criterio uniforme.
grazie anticipatamente...ciaooo ;););)
Prima di tutto devi sapere che qualsiasi operazione su gli alberi (INSERT, DELETE, MIN, MAX, SEARCH), ha un costo pari a lg n
l'algoritmo è:
for i = 1, . . . , n − 1 do
begin
inserisci in T un nodo di etichetta i
inserisci in T un nodo di etichetta n + i
end
visto che c'e' un for che deve essere eseguito n volte allora sara' n* le istruzioni dentro al for ossia inserisci in T un nodo di etichetta i e inserisci in T un nodo di etichetta n + i.
Come detto precedentemente l'operazione INSERT a un costo pari a lg n quindi abbiamo n * (lg n + lg n) [perche' abbiamo due INSERT]. Questo è uguale a .. n * (2lg n) = Ө (n*lg n). |
|
|
|
|
