Funzione O "O grande"

[winged_warrior]

Ma se io dico che una funzione è O(nlogm) e so che m>n possi dire che la funzione è O(logm)??

[Raptorista1]

Qualunque cosa tu voglia dire, innanzitutto dilla come si deve, e cioè utilizzando i compilatori di formule!!
Poi potremo discutere dei contenuti..

[winged_warrior]

Ma se io dico che una funzione è $O(nlogm)$ e so che $m>n$ posso dire che la funzione è $O(logm)$??

Io ho fatto questo ragionamento: date che $ m>n $ asintoticamente la mia funzione terrà conto solo della $m$ dato che è quella maggiore.

Non devo dimostrarlo rigorosamente. devo capire se posso pensare una cosa del genere.

[Raptorista1]

Puoi vederlo da solo applicando la definizione di "O grande" oppure cercando dei controesempi!

[dissonance]

Non è che significhi molto quello che hai scritto, winged_warrior. Parli di O grande, ma rispetto a cosa? Per $m \to infty$ e $n$ costante? Allora, se $n$ è solo una costante, $O(nlog(m))$ e $O(log(m))$ sono banalmente la stessa cosa.

[winged_warrior]

"dissonance":Non è che significhi molto quello che hai scritto, winged_warrior. Parli di O grande, ma rispetto a cosa? Per $m \to infty$ e $n$ costante? Allora, se $n$ è solo una costante, $O(nlog(m))$ e $O(log(m))$ sono banalmente la stessa cosa.

Guarda si tratta di valutare il tempo di esecuzione di un algoritmo.. praticamente quest'algoritmo ha due strutture dati che potenzialmente sono infinite. Possono avere però dimensioni diverse. e se la prima ha dimensione n e la seconda ha dimensione m, e se $n < m$ posso fare in modo che l'algoritmo ci metta $O(nlogm)$ e se so che posso togliere quella n perchè all'infinito è più piccola di m allora vorrei poter dire che il mio algoritmo ha tempo $O(logm)$