[Algoritmi] Complessità asintotica

Messaggioda minato91 » 22/10/2019, 10:21

Ciao a tutti,
avrei bisogno di una mano con lo studio delle complessità degli algoritmi per essere in grado di rispondere a domande come queste:

Siano f(n) e g(n) le complessità dell'algoritmo Chang & Roberts nel caso migliore e nel caso medio, rispettivamente. Quale delle seguenti relazioni asintotiche è falsa?
a) f(n) = Θ(g(n)) b) f(n) = O(g(n)) c) f(n) = o(g(n)) d) g(n) = Ω(g(n))

Siano f(n) e g(n) le complessità dell'algoritmo Chang & Roberts nel caso peggiore e nel caso medio, rispettivamente. Quale delle seguenti relazioni asintotiche è falsa?
a) f(n) = Θ(g(n)) b) f(n) = Ω(g(n)) c) f(n) = !(g(n)) d) f(n) = O(g(n))

Dove le complessità dell'algoritmo Chang & Roberts sono:
Θ(n^2) caso pessimo
Θ(n) caso ottimo
Θ(n log n) caso medio

La risposta alla prima domanda è la a, le risposte per la seconda sono a,d.
Conosco le differenze (a livello di definizioni) tra Θ,O e Ω ma non riesco ad applicarle su domande come queste.
Riuscite ad aiutarmi?
minato91
New Member
New Member
 
Messaggio: 40 di 96
Iscritto il: 07/02/2013, 17:27

Re: [Algoritmi] Complessità asintotica

Messaggioda vict85 » 22/10/2019, 15:08

Piccolo commento: usa le formule.

Codice:
$f = O(g)$

$f = O(g)$

Codice:
$f \in o(g)$

$f = o(g)$

Codice:
$f = \Omega(g)$

$f = \Omega(g)$

Codice:
$f \in \Theta(g)$

$f = \Theta(g)$

Venendo ai tuoi esercizi, si tratta semplicemente di usare ciò che sai. Hai che \(f(n) = \Theta(n)\) e \(g(n) = \Theta(n\log n)\).

Per il primo esercizio, nel punto a, ti chiede se \(\Theta(n) = f(n) = \Theta\bigl(g(n)\bigr) = \Theta( n\log n )\). Ovviamente è falsa. Similmente mostri che b, c e d sono vere.

Il secondo esercizio è simile.
vict85
Moderatore
Moderatore
 
Messaggio: 9898 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Complessità asintotica

Messaggioda minato91 » 23/10/2019, 13:58

Intanto grazie per la risposta. Credo di avere difficoltà nell'applicare le regole.
Ad esempio $f(n) = O(\Theta(n))$ è sempre equivalente a $f(n) = O(n)$ ? Cioè, $\Theta$ può essere in ogni caso omessa? E che succede invece nei casi in cui abbiamo ad esempio $f(n) = \Omega(O(n))$ ? Come viene letta la parte destra?
minato91
New Member
New Member
 
Messaggio: 41 di 96
Iscritto il: 07/02/2013, 17:27

Re: [Algoritmi] Complessità asintotica

Messaggioda vict85 » 23/10/2019, 16:48

Per prima cosa, valgono le seguenti proprietà/definizioni:
  • \( f = O( g ) \) se e solo se \(\displaystyle \forall k > 0,\,\exists n_0,\,\forall n > n_0,\; \lvert f(n)\rvert \le \lvert kg(n) \rvert \);
  • \( f = \Omega( g ) \) se e solo se \( g = O( f ) \);
  • \( f = \Theta( g ) \) se e solo se \( f = O( g ) \wedge f = \Omega( g ) \);
Nota inoltre che sarebbe più appropriato scrivere \( f \in O( g ) \) piuttosto che \( f = O( g ) \), dato che \(O(n)\) è di fatto un sottoinsieme dell'insieme delle funzioni.
Detto questo, la relazione \(f \preceq g \Leftrightarrow f = O( g )\) è una relazione di ordine (insomma è riflessiva, antisimmetrica e transitiva), così come la relazione \(f \succeq g \Leftrightarrow f = \Omega( g )\). Invece, la relazione \(f \sim g \Leftrightarrow f = \Theta( g )\) è una relazione di equivalenza (riflessiva, simmetrica e transitiva).

Usando la proprietà transitiva è evidente che \(f = \Omega( \Omega( g ) ) \Rightarrow f = \Omega( g )\), \(f = \Theta( \Theta( g ) ) \Rightarrow f = \Theta( g )\), \(f = O( O( g ) ) \Rightarrow f = O( g )\). Inoltre, siccome \(f = \Theta( g ) \Rightarrow f = \Omega( g )\) e \(f = \Theta( g ) \Rightarrow f = O( g )\), si ricava facilmente che \(f = \Omega( \Theta( g ) ) \Rightarrow f = \Omega( g )\) e \(f = O( \Theta( g ) ) \Rightarrow f = O( g )\). Similmente, si può osservare che \(f = \Theta( \Omega( g ) ) \Rightarrow f = \Omega( g )\) e \(f = \Theta( O( g ) ) \Rightarrow f = O( g )\).
Gli insiemi \(\Omega( O(n) )\) e \(O( \Omega(n) )\) non sono ben definiti e non vanno mai usati.
vict85
Moderatore
Moderatore
 
Messaggio: 9902 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Complessità asintotica

Messaggioda minato91 » 24/10/2019, 15:40

E fin qui sei stato chiarissimo. Però mi è capitato che in alcuni esercizi compaia :

$f(n) = o(g(n))$
con
$g(n) = O(n log n)$
e
$f(n) = \Theta(log n)$

oppure

$f(n) = O(g(n))$
con
$g(n) = o(n log n)$
e
$f(n) = \Theta(log n)$

Come vanno gestite?
minato91
New Member
New Member
 
Messaggio: 42 di 96
Iscritto il: 07/02/2013, 17:27

Re: [Algoritmi] Complessità asintotica

Messaggioda vict85 » 24/10/2019, 16:45

\(\omicron(g)\) è il complementare in \(O(g)\) di \(\Theta(g)\). Insomma \(f = \omicron(g) \rightarrow f = O(g)\) e \(f = \omicron(g) \rightarrow f \neq \Theta(g)\). Similmente \(f = o(g) \rightarrow f \neq \Omega(g)\).

In generale, quando trovi che \(f = \Theta(\log n)\) in questi esercizi, puoi tranquillamente sostituire tutte le \(f\) con delle \(g\) e viceversa. Quindi ignoro \(\Theta\). Detto questo non è vero che per ogni \(g = O(n\log n)\) e \(f = \Theta(\log n)\) si abbia \(f = \omicron(g)\). Basta infatti porre \(g = 1\), \(g = n\) o \(f = g\) per trovare un controesempio.

Nota che una cosa è dire che se \(f = O(g)\) e \(g = O(h)\) allora \(f = O(h)\). Un'altra è prendere un qualsiasi \(g = O(h)\) e dire che \(f = O(g)\). In quest'ultimo caso, si sta in pratica imponendo che si abbia \(f = O(1)\).
vict85
Moderatore
Moderatore
 
Messaggio: 9913 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Complessità asintotica

Messaggioda apatriarca » 24/10/2019, 17:55

In termini un po' meno astratti, nel primo esempio le espressioni si traducono semplicemente nella seguente relazione
\[ \exists k \in \mathbb R^+, \forall \epsilon \in \mathbb R^+, \delta = \epsilon\,k \exists N \in \mathbb N, \forall n > N \quad |f(n)| < \epsilon\,g(n) \leq \epsilon\,k\,n\,\log n = \delta\,n\,\log n. \]
Cioè \( f(n) \in o(n\,\log n) \). Si tratta di una limitazione superiore. La funzione può benissimo logaritmica (o lineare o costante o ..).

Un discorso completamente analogo si ha nel secondo caso. La relazione è la stessa con solo lo scambio di \(k\) ed \(\epsilon\) e poco altro.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5302 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite