Esercizio Notazione Asintotica (Teorico)
Mi trovo alle prese con questo esercizio:
Definire la notazione $ Θ $ e discuterne il significato.
Rispondere poi ad ognuna delle seguenti domande, motivando la risposta:
1. Se si dimostra che un algoritmo ha tempo di esecuzione $ O(n^2) $ nel caso
peggiore, è possibile che in qualche caso l'algoritmo termini in $ O(n) $ passi?
2. Se si dimostra che un algoritmo ha tempo di esecuzione $ O(n^2) $ nel caso
peggiore, è possibile che l'algoritmo termini in $ O(n) $ passi in tutti i casi?
3. Se si dimostra che un algoritmo ha tempo di esecuzione $ Θ(n^2) $ nel caso
peggiore, è possibile che in qualche caso l'algoritmo termini in O(n) passi?
4. Se si dimostra che un algoritmo ha tempo di esecuzione $ Θ(n^2) $ nel caso
peggiore, è possibile che l'algoritmo termini in $ O(n) $ passi in tutti i casi?
Mia Soluzione:
Definizione notazione Θ: $ f(n) = \Theta(g(n)) $
se $ EE c1,c2,n0 : AA n >= n0 , c1 g(n) <= f(n) <= c2 g(n) $
se il limite superiore di f(n) è uguale al limite inferiore di f(n) si può dire che è f(n) è strettamente limitata e si indica appunto con $ Θ $
1)è possibile per un particolare input,ad esempio nell'insertion sort nel caso in cui l'array sia già ordinato
2)non è possibile perchè altrimenti il tempo di esecuzione nel caso peggiore sarebbe stato O(n)
3)è possibile perchè $ Theta(n^2) sube O(n) $
4) non è possibile perchè altrimenti l'algoritmo avrebbe avuto un tempo di esecuzione nel caso peggiore pari a O(n)
Ho risposto in modo corretto?
Definire la notazione $ Θ $ e discuterne il significato.
Rispondere poi ad ognuna delle seguenti domande, motivando la risposta:
1. Se si dimostra che un algoritmo ha tempo di esecuzione $ O(n^2) $ nel caso
peggiore, è possibile che in qualche caso l'algoritmo termini in $ O(n) $ passi?
2. Se si dimostra che un algoritmo ha tempo di esecuzione $ O(n^2) $ nel caso
peggiore, è possibile che l'algoritmo termini in $ O(n) $ passi in tutti i casi?
3. Se si dimostra che un algoritmo ha tempo di esecuzione $ Θ(n^2) $ nel caso
peggiore, è possibile che in qualche caso l'algoritmo termini in O(n) passi?
4. Se si dimostra che un algoritmo ha tempo di esecuzione $ Θ(n^2) $ nel caso
peggiore, è possibile che l'algoritmo termini in $ O(n) $ passi in tutti i casi?
Mia Soluzione:
Definizione notazione Θ: $ f(n) = \Theta(g(n)) $
se $ EE c1,c2,n0 : AA n >= n0 , c1 g(n) <= f(n) <= c2 g(n) $
se il limite superiore di f(n) è uguale al limite inferiore di f(n) si può dire che è f(n) è strettamente limitata e si indica appunto con $ Θ $
1)è possibile per un particolare input,ad esempio nell'insertion sort nel caso in cui l'array sia già ordinato
2)non è possibile perchè altrimenti il tempo di esecuzione nel caso peggiore sarebbe stato O(n)
3)è possibile perchè $ Theta(n^2) sube O(n) $
4) non è possibile perchè altrimenti l'algoritmo avrebbe avuto un tempo di esecuzione nel caso peggiore pari a O(n)
Ho risposto in modo corretto?
Risposte
secondo me ti sei un po' confuso con la notazione... le risposte dovrebbero essere:
1 e 2) si perchè O è una limitazione dall'alto, il fatto che il tempo nel caso peggiore sia $O(n^2)$ pertanto non esclude che sempre nel caso peggiore il tempo possa essere $O(n)$, solo che magari non si è ancora riusciti a dimostrare una limitazione più stretta.
3) si perchè non sappiamo nulla sul caso migliore, che per quanto ne sappiamo potrebbe anche concludersi quindi in tempo lineare o meglio (magari anche costante).
4) no perchè nel caso peggiore avremmo una limitazione dal basso di $n^2$ e una dall'alto di $n$, il che è chiaramente assurdo
1 e 2) si perchè O è una limitazione dall'alto, il fatto che il tempo nel caso peggiore sia $O(n^2)$ pertanto non esclude che sempre nel caso peggiore il tempo possa essere $O(n)$, solo che magari non si è ancora riusciti a dimostrare una limitazione più stretta.
3) si perchè non sappiamo nulla sul caso migliore, che per quanto ne sappiamo potrebbe anche concludersi quindi in tempo lineare o meglio (magari anche costante).
4) no perchè nel caso peggiore avremmo una limitazione dal basso di $n^2$ e una dall'alto di $n$, il che è chiaramente assurdo
un'altra cosa,perchè il caso migliore di alcuni algoritmi di ordinamento su wikipedia è indicato con O invece di $ \Omega $ ?
nessuno sa rispondermi? 
"Andrew Ryan":
un'altra cosa,perchè il caso migliore di alcuni algoritmi di ordinamento su wikipedia è indicato con O invece di $ \Omega $ ?
Ci potrebbero essere tantissimi motivi. Devi capire che wikipedia, soprattutto quella italiana, non è una fonte particolarmente affidabile. Come dimostra anche "l'aiuto del pubblico" in "Chi vuole essere Milionario", la cultura non è democratica. Volendo comunque selezionare alcune possibili motivazioni (considerando anche che non ci hai fornito esempi di tale uso):
1. L'autore è poco preciso con le notazioni. La O viene infatti usata spesso in modo poco formale per indicare delle complessità di qualsiasi tipo. Soprattutto in contesti relativamente poco formali o in cui è più difficile usare la notazione corretta.
2. L'autore potrebbe essere normalmente abbastanza preciso nelle notazioni, ma potrebbe essersi sbagliato in quell'occasione.
3. L'autore ha usato il simbolo in maniera corretta, ma tu hai frainteso la sua frase.
In ogni caso credo che sia meglio fare affidamento al tuo manuale di testo invece che a wikipedia.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo