Master Theorem - Comportamento asintotico successioni per ricorrenza
Inviato: lunedì 25 giugno 2018, 4:36
Prima di tutto ci tengo a ringraziare il Prof. Gobbino per le utilissime e chiarissime lezioni che gentilmente ha deciso di condividere con "il popolo di internet", a cui appartengo; ma vengo subito al punto.
Studio ing. informatica, e in un corso di algoritmi che sto frequentando mi è sorto un problema di carattere matematico, sulle successioni per ricorrenza. Queste sono tirate in ballo quando si cerca la complessità (efficenza) asintotica di un algoritmo, definita come "quanto impiega un algoritmo, su un dato input di lunghezza n, a portarsi a termine".
In breve è una funzione T : N --> N debolmente crescente, in cui l'immagine è da intendersi come numero di passi compiuti dall'algoritmo, dato l'input. Di questa funzione si è interessati a capire il comportamento asintotico per n-->+inf, ovvero a dare una stima di T tramite O-grande, Theta (asintoticità a meno di una costante davanti) etc. Solitamente T è data come soluzione di un eq. alle ricorrenze, esempio:
T(n) = T(n/3) + Theta(log(n))
Come si comporta T all'infinito? Essendo debolmente crescente ammette limite e si vede che è +inf, ma non serve a molto nell'analisi senza capire in che modo questa ci tenda.
Mi chiedevo come approcciare in modo rigoroso un problema di questo tipo. Malgrado i miei sforzi, non sono riuscito a venirne a capo. Chiedo quindi aiuto a lei, o a chiunque sappia aiutarmi.
P.S. Nei corsi di informatica equazioni come queste vengono risolte affidandosi al cosiddetto "Master Theorem", applicato "bovinamente" e senza capirne il senso.
Studio ing. informatica, e in un corso di algoritmi che sto frequentando mi è sorto un problema di carattere matematico, sulle successioni per ricorrenza. Queste sono tirate in ballo quando si cerca la complessità (efficenza) asintotica di un algoritmo, definita come "quanto impiega un algoritmo, su un dato input di lunghezza n, a portarsi a termine".
In breve è una funzione T : N --> N debolmente crescente, in cui l'immagine è da intendersi come numero di passi compiuti dall'algoritmo, dato l'input. Di questa funzione si è interessati a capire il comportamento asintotico per n-->+inf, ovvero a dare una stima di T tramite O-grande, Theta (asintoticità a meno di una costante davanti) etc. Solitamente T è data come soluzione di un eq. alle ricorrenze, esempio:
T(n) = T(n/3) + Theta(log(n))
Come si comporta T all'infinito? Essendo debolmente crescente ammette limite e si vede che è +inf, ma non serve a molto nell'analisi senza capire in che modo questa ci tenda.
Mi chiedevo come approcciare in modo rigoroso un problema di questo tipo. Malgrado i miei sforzi, non sono riuscito a venirne a capo. Chiedo quindi aiuto a lei, o a chiunque sappia aiutarmi.
P.S. Nei corsi di informatica equazioni come queste vengono risolte affidandosi al cosiddetto "Master Theorem", applicato "bovinamente" e senza capirne il senso.