Notazione asintotica

Notazione asintotica

Messaggioda gianni80 il sab 5 nov 2011, 16:56

Quale è il significato della costante "c" che compare nella definizione di "O grande"?
gianni80
 
Messaggi: 166
Iscritto il: gio 19 nov 2009, 14:44

Messaggioda salvo.tringali il sab 5 nov 2011, 17:06

Cosa intendi? Prendiamo due successioni, f e g, a valori in \mathbb{R}. Si scrive f = O(g) e si legge "esiste c > 0 tale che |f(n)| \le c\;\! |g(n)| per ogni n \in \mathbb{N}." Il tuo dubbio qual è?
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Messaggioda rrronny il sab 5 nov 2011, 17:10

salvo.tringali ha scritto:Cosa intendi? Prendiamo due successioni, f e g, a valori in \mathbb{R}. Si scrive f = O(g) e si legge "esiste c > 0 tale che |f(n)| \le c\;\! |g(n)| per ogni n \in \mathbb{N}." Il tuo dubbio qual è?

Non proprio...

Siano f,g: A \to B due funzioni. Si dice che f(x) = O(g(x)) se esistono \mathbb{R} \ni c>0 e un valore x_0 \in A tale che \forall x  \ge x_0 si abbia f(x) \le  c \, g(x).

gianni80 ha scritto:Quale è il significato della costante "c" che compare nella definizione di "O grande"?

Cosa intendi per "significato" di un segno, Gianni? I singoli segni non hanno mai un significato, infatti li puoi cambiare come vuoi, semmai è la relazione fra i segni che fornisce un senso globale a un assunto.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Messaggioda gianni80 il sab 5 nov 2011, 17:41

Intendevo il significato nella teoria degli algoritmi, cioè perchè limito superiormente una funzione f(n) (che rappresenta il tempo di esecuzione) con cg(n) e non semplicemente con g(n)?
Cosa mi rappresenta quella costante "c", quale idea intuitiva si vuole catturare all'interno della teoria degli algoritmi?
gianni80
 
Messaggi: 166
Iscritto il: gio 19 nov 2009, 14:44

Messaggioda salvo.tringali il sab 5 nov 2011, 18:17

@rrronny. Presta attenzione, moi si è riferito solamente al caso delle successioni (di segno arbitrario) per cui l'unico punto di accumulazione è all'infinito (ed è questo il caso rilevante nell'ambito della teoria della complessità per gli algoritmi).
@gianni. L'idea è che il grafico di f si sviluppa, a meno di una costante di scala, fra il grafico di -|g| e il grafico di |g|.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Messaggioda rrronny il sab 5 nov 2011, 18:18

Click.
A quanto ne so, si usa l'o grande, sia perché spesso nei calcoli non serve una precisione maggiore (anche nella matematica pura è così) e/o non si riesce a realizzarla; sia perché, a volte, avendo a che fare con macchine reali, il tempo di esecuzione può variare stocasticamente in un certo range.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Messaggioda gianni80 il sab 5 nov 2011, 18:46

@salvo. Perchè a meno di questa costante di scelta, che significato ha questa costante?
gianni80
 
Messaggi: 166
Iscritto il: gio 19 nov 2009, 14:44

Messaggioda fry il sab 5 nov 2011, 21:31

gianni80 ha scritto:Quale è il significato della costante "c" che compare nella definizione di "O grande"?

La costante non ha significato per la maggior parte delle applicazioni, ad esempio un algoritmo che richiede O(n^2) operazioni sarà migliore di uno che ne richiede O(n^2 \log \log n), poi quali siano le costanti "all'interno" degli O grande ha poco importanza per n sufficientemente grande.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Messaggioda gianni80 il mar 8 nov 2011, 14:34

Supponiamo che un algoritmo abbia tempo di esecuzione f(n)="numero enorme"*n e consideriamo la funzione g(n)=n. Tutte e due le funzioni stanno in O(n) ma tra le due funzioni c'è una differenza abissale in termini di esecuzione. Un altro esempio potrebbe essere f(n)="numero enorme" e g(n)=1
(cioè non dipendenete dalla taglia dell'input) in questo caso le due funzioni stanno in O(1) ma danno informazioni completamente diverse sul tempo di esecuzione. Quindi la domanda è: perchè funzioni così diverse vengono messe nello stesso insieme nella teoria degli algoritmi?

Possibile risposta.
Premessa.
Ogni algoritmo esegue un insieme di operazione di base elementare, se si implementao queste operazioni con una macchina e se supponiamo che tutte le operazioni hanno lo stesso costo (che chiamiamo costo di implementazione) allora il tempo di esecuzione di una algoritmo è uguale al numero di operazioni effettuate per il costo di implementazione.

Consideriamo adesso una macchina M, supponiamo di costo unitario di un secondo, e supponiamo che un algoritmo A rispetto alla macchina M abbia complessità di tempo f(n)=O(g(n)). Questo vuol dire che f(n) \leq cg(n) definitivamente o equivalentemente \frac{1}{c}f(n) \leq g(n).
Adesso supponiamo di essere sufficientement bravi a costruire una macchina M' con costo di implementazione 1/c allora il tempo di esecuzione dell'algoritmo A su questa macchina sarà T(n)=\frac{1}{c}f(n)da cui T(n) \leq g(n) cioè T(n) è limitata superiormente da g(n).
Quindi dire che un algorimto A ha tempo f(n)=O(g(n)) vuol dire che esiste un fattore di scala temporale k tale che se si è in grado di costruire una macchina M che implementa le operazioni di base con un costo pari a k allora il tmepo di A, che gira su M, è limitato superiormente da g.
In definitiva f=O(g) ci dice che f è limitatata superiormente da g a meno del modo in cui vengono implementate le operazioni di base da parte di un modello di calcolo.

Che ne pensate?
gianni80
 
Messaggi: 166
Iscritto il: gio 19 nov 2009, 14:44

Messaggioda salvo.tringali il mar 8 nov 2011, 14:45

...ma infatti lo studio asintotico della complessità in termini degli O grandi è spesso e volentieri sostituito da un'analisi più profonda in cui le costanti vengono appunto esplicitate. Sono due approcci diversi allo stesso problema. In alcuni contesti, ci si contenta di avere una stima asintotica in termini di O grandi (e il discorso non vale soltanto per la teoria della complessità degli algoritmi - penso, per dire, alle stime asintotiche delle funzioni dei divisori, della phi di Eulero, della funzione enumeratrice dei primi, etc nell'ambito della teoria dei numeri analitica). In altri, invece, è importante e utile determinare, ad es., la minima costante positiva per cui sussiste una certa maggiorazione.

Nel caso della teoria degli algoritmi, si assume che le implementazioni siano tutte riferite ad un stesso modello ideale del calcolatore (per quel che ricordo, la macchina di von Neumann), e una stima asintotica in termini di O grandi indica semplicemente l'esistenza di una qualche implementazione (non necessariamente ottimale) dell'algoritmo in oggetto la cui complessità (espressa in numero di operazioni elementari eseguite dalla macchina per terminare l'esecuzione del programma per una qualsiasi dimensione, n, del problema da doversi risolvere) non è maggiore di una costante assoluta, C, moltiplicata per un certo bound variabile in funzione di n.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Prossimo

Torna a Algoritmi e strutture dati

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite