Metodo di sostituzione per la risoluzione di una ricorrenza

[dlbp]

Il è un limite che limita (mi scuso per il gioco di parole) sia superiormente che inferiormente: secondo me è palese che la somma tra quei due termini debba dare a sua volta un dato che il limite inferiore del theta incide comunque nella somma e perché il limite superiore è valido per entrambi i termini.

Forse mi sono espresso con i piedi

Dimmi un po' te fairyvilje

[fairyvilje]

Si il concetto è quello. I termini di ordine sublineare nella funzione in di fatto non vanno a influire sul lower bound di che è pure lineare. Quindi la somma resta un

Si può anche risolvere esplicitamente con un paio di disequazioni ma non mi pare proprio il caso .

[dlbp]

In poche parole il ragionamento che ho fatto io è il seguente:
dato che ho un limite inferiore dato dal , allora la somma con un non potrà mai essere al di sotto del limite inferiore dato dal dato che la funzione che è un non mi permetterà mai di scendere al di sotto di quel limite.

Che ne dici? Mi merito una "mazzata"?

Questa somma caratterizza il tempo di esecuzione di un algoritmo di cui devo graficare i tempi di esecuzione.

[fairyvilje]

Niente bastoni, mazze o armi varie .
Ora però sono curioso. Come fai a graficare i tempi di esecuzione per un algoritmo usando un comportamento asintotico? . La cosa non mi pare molto sensata dato che manca quasi tutto per poter graficare qualcosa D:

[dlbp]

No, mi son espresso io in malo modo.
Devo graficare i tempi di esecuzione (che ho già "catturato" tramite il compilatore) per diversi valori di n.

Il mio obbiettivo è quello di dimostrare proprio la correttezza della notazione asintotica.

[fairyvilje]

Ok, ora è chiaro ;)

[dlbp]

fairyvilje buongiorno. Volevo farti una domanda. Per dimostrare la correttezza della notazione asintotica, dopo aver graficato i tempi di esecuzione devo cercare di stringere "il più possibile" i limiti superiori o inferiori? O posso anche trovarli laschi?

Grazie

[fairyvilje]

Mi dispiace ma è proprio impossibile dimostrare la correttezza di una notazione asintotica avendo a disposizione un grafico che considera un numero limitato di casi.
Al contrario puoi dire che in una certa regione l'algoritmo sembra avere un comportamento "quello-che-è".
Per dimostrare qualcosa devi cambiare approccio: tutti i test di questo pianeta non sarebbero sufficienti. Una cosa che si potrebbe fare è l'analisi del caso peggiore attraverso il grafo equivalente del tuo codice. Se posti l'algoritmo possiamo lavorarci sopra.

[dlbp]

Beh...guarda....il docente ci ha chiesto di prendere i tempi di esecuzione della funzione (logicamente per ragioni di spazio e ragionevolezza l'ho dovuto fare per determinati valori di n) e verificare proprio la correttezza dell'analisi asintotica riportando il grafico con Matlab.

Il codice lo posterei ma è una marea di codice
Puoi spiegarmi in parole povere o allegando un pdf cosa è il grafo equivalente del codice?

Grazie

[fairyvilje]

Prima di risponderti possa sapere cosa studi? Almeno da "tarare" la risposta.