Salve, una domanda riguardante il secondo esercizio. Sapendo che a ogni livello abbiamo 2^i nodi, e che ognuno di questi nodi costa (n/2^i)^2 e che quindi il costo complessivo di ogni livello è n^2 / 2^i , per trovare il risultato finale si puo' fare in questo modo ? --> (log n + 1) * (n^2 / 2 ^ log n) cioè sto considerando l'altezza dell'albero + 1 siccome partiamo da 0, e la sto sommando al costo totale di ogni livello che abbiamo detto essere n^2 / 2^i , dove al posto della i metto log n siccome è l'altezza k massima, e così ottengo un prodotto dove il termine più rilevante è chiaramente n^2, quindi scarto gli altri, e arrivo alla conclusione Theta(n^2) ? questo sarebbe il procedimento più logico per me , siccome non sono abituato a usare sommatorie. Mi riesce a dire se ha senso?
Ciao, grazie davvero di aver visto e commentato il mio video. Si vero, la parentesi è moltiplicata per 2 ma al fine del calcolo asintotico il 2 perde il suo valore, perché un n al quadrato per una costante sempre dell’ordine al quadrato rimane.
Se l’equazione ricorsiva ha come coefficiente a un valore frazionario come gestisco l’albero ?
Salve, una domanda riguardante il secondo esercizio. Sapendo che a ogni livello abbiamo 2^i nodi, e che ognuno di questi nodi costa (n/2^i)^2 e che quindi il costo complessivo di ogni livello è n^2 / 2^i , per trovare il risultato finale si puo' fare in questo modo ? --> (log n + 1) * (n^2 / 2 ^ log n) cioè sto considerando l'altezza dell'albero + 1 siccome partiamo da 0, e la sto sommando al costo totale di ogni livello che abbiamo detto essere n^2 / 2^i , dove al posto della i metto log n siccome è l'altezza k massima, e così ottengo un prodotto dove il termine più rilevante è chiaramente n^2, quindi scarto gli altri, e arrivo alla conclusione Theta(n^2) ? questo sarebbe il procedimento più logico per me , siccome non sono abituato a usare sommatorie. Mi riesce a dire se ha senso?
Complimenti per il video!
Potresti portare sul canale La Torre di Hanoi?
Ok si è un video che vorrei preparare. Grazie per il commento 😊
Ciao, perchè nel primo esempio per il calcolo di T(n) non hai usato una sommatoria mentre nel secondo esempio si?
Ciao, perché nel primo caso avevo un costo costante ad ogni livello quindi il calcolo mi veniva automatico senza fare il passaggio con la sommatoria.
@@Algoritmi01 il costo costante di cui parli è il costo complessivo per livello?
@13:40 quando tifi fuori n^2 non dovrebbe rimanere 1/(2^i)? perché elevi tutta la frazione alla i?
Ciao, si certo ma è la stessa cosa, perché 1 elevato alla i è sempre 1 😊
@@Algoritmi01 Vero, grazie, era una cosa banalissima
😉
MADO GRAZIE adesso ho capito come si fa
Sono veramente super contenta di questo 🤗
Ciao, la complessità non dovrebbe essere T(n)=O(n^2 logn) ?
Spiegazione perfetta
Alla fine,minuto 15.45 ,non verrebbe 2 moltiplicato alla parentesi che si avvicina a 1 e dunque 2?
Ciao, grazie davvero di aver visto e commentato il mio video. Si vero, la parentesi è moltiplicata per 2 ma al fine del calcolo asintotico il 2 perde il suo valore, perché un n al quadrato per una costante sempre dell’ordine al quadrato rimane.
Gli alberi di ricorsione possono dare una stima esatta del costo di un algoritmo?
Beh si sono un metodo risolutivo delle equazioni di ricorrenza.
Qual è senza apostrofo!
E si vede che sono antica! Ma per fortuna parlo di algoritmi e non di lingua italiana 😉