Simboli di Landau

[ZfreS]

Aprirò probabilmente l'ennesimo thread sull'argomento, ma non ho trovato nulla che risponda alla mia domanda. C'è un po di confusione sui simboli di Landau. Per ogni simbolo c'è una definizione che fa uso del limite (alla quale mi sono affezionato) e un'altra che fa uso di una diseguaglianza, che non mi sembra avere lo stesso effetto, mi sembra un po "debole". C'è chi dice che sono equivalenti, c'è chi afferma il contrario, chi dice che la definzione standard è quella col limite, c'è chi dice che è più appropriata l'altra. Leggend molti post non ho fatto altro che aumentare la mia confusione, su un argomento che ancora non avevo studiato. Potreste per favore chiarimi come stanno le cose. Avendo iniziato a studiare l'argomento su youmath, che mi sembra sia ben documentato, ho visto una serie di proprietà come per esempio $f(x)*O(g(x)) = O(f(x)*g(x))$ oppure
$O(g_1(x))+O(g_2(x)) = O(|g_1(x)| + |g_2(x)|)$.
Ptreste spiegarmi per favore come andrebbero dimostrate queste e altre proprietà? Io ho tentato di utlizzare la definzione del limite, ma senza riusciurci.

[pilloeffe]

Ciao ZfreS,

Magari l'hai già fatto, ma nel dubbio... Hai già dato un'occhiata a questo tutorial, che al momento si trova giusto sopra il tuo post?

[gugo82]

Youmath ben documentato?

Ad ogni buon conto, se continui ad usare un limite con $"O"$ non vai da nessuna parte...

[ZfreS]

Grazie pilloeffe! Ma non capisco perchè su molti libri/dispense/siti viene fornita la definzione col limite se la condizione di esistenza del limite non è necessaria. Youmath mi è sembrato sempre un sito serio.

[ZfreS]

Riprendo l'argomento perchè sono troppo confuso sui simboli di Landau. Il problema è che li sto affrontando studiando la complessità computazionale degli algoritmi. Li ho sfiorati quando studiai la serie e il polinomio di Taylor, in cui i termini meno significativi venivano indicati con o-piccolo. Stando alla definizione che da gugo, per dimostrare che una funzione $f(n) in Theta(g(n))$ (lo stesso vale per O-grande e per gli altri) bisogna ricorre alla definzione per cui trovare $c_1, c_2, n_0$ positivi, tali che $0<=c_1g(n)<=f(n)<=c_2g(n)$, oppure stando alle definzioni che fanno uso del limite, dimostrare ciò calcolando il limite? Il libro da cui studio algoritmi sceglie la prima strada e a detta di gugo il caso con il limite è un caso particolare, tuttavia c'è una grossa discordanza in quanto molti libri autorevoli (quindi non solo youmath) riportano. Sinceramente non capisco perchè si usa o l'una o l'altra pur non essendo equivalenti, oppure per qualcuno lo sono e per qualcuno no?

[gugo82]

Ma non capisco perchè su molti libri/dispense/siti viene fornita la definzione col limite se la condizione di esistenza del limite non è necessaria.

Semplicemente, chi le propone “canta la mezza messa” perché per gli usi che ne deve fare e per le funzioni che incontra non è necessario lavorare di fino.

Youmath mi è sembrato sempre un sito serio.

Perché non hai mai visto gli amministratori venirsi a lamentare del fatto che loro utenti chiedessero su queste pagine chiarimenti su quanto riportato nelle loro “dispense”…

[ZfreS]

Capisco..., quindi la definizione più fine trova applicazione nell'analisi della complessità computazionale, invece la'ltra definzione serve solo per fare calcoli e cercare di trasmettere un'idea intuitiva di cioò che succede. Stando alla mia domanda, per dimostrare che una funzione appartiene a $Theta(g(n))$ piuttosto che $O(g(n))$, devo ricorrere per forza alla definzione come ho visto fare fino adesso (anche se non c'è una procedura del tutto chiara), oppure esiste un altro metodo?

[gugo82]

Beh, dipende.
In generale per $f in Theta(g)$ ti basta che $f in text(O)(g) ^^ g in text(O)(f)$; se $g != 0$ affinché ciò sia vero basta che $|f/g|$ sia limitata e per quest’ultima ti basta che esista finito e non nullo il $lim |f/g|$.
Mentre per $f in text(O)(g)$ ti serve mostrare che, se $ g != 0$, il rapporto $|f/g|$ è definitivamente limitato superiormente, cioè che $text(maxlim) |f/g|$ esiste finito.

[ZfreS]

Mi sarebbe più utile capire con un esempio. Se devo dimostrare che $((n), (k)) in Theta(n^k)$, in che modo devo verificare ciò che hai scritto?

[gugo82]

basta che esista finito e non nullo il $lim |f/g|$.