Complessità computazionale - ho bisogno di chiarimenti

[dleonard]

ciao ragazzi...

chiedo aiuto a tutti gli studenti di informatica per alcuni chiarimenti

chi mi dice qual'è l'ordine di complessità di questo algoritmo?

potreste spiegarmi (mi basta a grandi linee) i calcoli svolti?

considerate che c'è un errore di battitura..l'assegnamento del ciclo for m:= n-2 è errato...sarebbe in realta m:=m-2...

[macfaber]

Questo topic mi ha fatto tornare indietro ai tempi dell'università!!... Ad occhio sembra che l'algoritmo calcoli n volte n per n + j e che questo calcolo si moltiplica n - 10 volte e nel caso peggiore in cui n sia > 44, la funzione viene chiamata ricorsivamente ...

Purtroppo, e mi vergogno a dirlo, sono un pò arruginito considerando che questa materia l'avrò data nel '99 quando ero al primo anno e mi sono dimenticato tutto almeno per quanto riguarda la teoria...

Però se il problema non è esponenziale, è abbastanza vicino ad esserlo :-)

Sorry e in bocca al lupo!

[dleonard]

io avevo calcolato un O(n^3) nel caso pessimo (n>44)

e O(n^2) nel caso n<44, dato che il while viene comunque eseuito...

ma la soluzione dice che nel caso n<44 la complessità O(1), quindi costante! ma a me sembra strano perchè, è vero che MISTERO:=1 richiede tempo costante, ma il while, come gia detto viene eseguito in ogni caso!!

[dleonard]

ma come è possibile? l altro giorno tutti a fare i fighi a parlare di greedy e backtrack, e oggi nessuno??

scherzo ovviamente, ma se qualcuno può chiarirmi questa cosa sarei felicissimo...

[redvex]

ora son troppo stanco per calcolarla, ma appena mi riprendo te lo svolgo e ti trovo l'eq di ricorrenza

[zzi_miei]

ciao,

spero di non dire troppe cazzate, pero' secondo me O(1) e' giusto.provo a spiegarmi:

se n fosse uguale a 44 puoi calcolare il numero esatto di iterazioni del while e del for (dovrebbe essere 18*44, giusto?). Se utilizzi questo numero come costante c nella definizione di O allora per tutti i valori di n tra 0 e 44 la formula espressa con questa costante e' vera (cioe' rappresenta un limite asintotico superiore). prova ad immaginare una retta costante con intercetta=18*44. tutte le chiamate mistero(n<=44) sono sotto quella retta.

[BlackICE]

Hmm... a me qualcosa non mi torna... quel O(1) mi puzza

Come la vedo io:

1) n≥44: O(n^3) ---> fa i due cicli innestati e fa anche la ricorsione

2) 44≥n≥10: O(n^2) ---> fa i due cicli innestati ma non la ricorsione

3) n≤10: θ(n) ----> fa soltanto il for interno che cicla esattamente n volte

Il ragionamento di zzi_miei invece non mi torna: anche per n="un qualsiasi numero > 44" si può contare l'esatto numero di cicli che verranno fatti e, data la definizione di funzione di complessità come di una funzione monotona non-decrescente, è naturale che per tutti i valori di n sotto quella soglia scelta l'algoritmo starà sotto quella complessità.

Calcolare la complessità di un algoritmo vuol dire valutare, spesso in ordine di grandezza a causa della complessità dei conti da fare, come varia il tempo "di esecuzione" al variare della dimensione dell'input. Non è un semplice trovare un "limite" al tempo "di esecuzione" dell'algoritmo. Per esempio: dire che un algoritmo è O(n^2) vuol dire che se la dimensione dell'input aumenta di 3 volte allora il tempo "di esecuzione" dell'algoritmo aumenta, nel caso peggiore, di 9 volte.

Almeno queste sono le cose che mi ricordo io...

Se ho detto castronerie correggetemi.

p.s: non sapevo come spiegarmi ma si sa che un algoritmo non ha un tempo di esecuzione

[zzi_miei]

scusa ma se n<= 10 nel while non entra e quindi neanche nel for.

a parte questo, fino a 44 la complessita' non dipende dalla dimensione dell'input o meglio ne dipende ma la puoi limitare superiormente con una costante. per n>44 la devi calcolare come funzione di n semplicemente perche' non sai quanto potra' valere.

[BlackICE]

scusa ma se n<= 10 nel while non entra e quindi neanche nel for.

a parte questo, fino a 44 la complessita' non dipende dalla dimensione dell'input o meglio ne dipende ma la puoi limitare superiormente con una costante. per n>44 la devi calcolare come funzione di n semplicemente perche' non sai quanto potra' valere.

Ooops

Per n < 10 hai ragione... niente cicli e niente ricorsione => O(1)

Per il discors n > 44 mi sa che non mi sono spiegato. Premesso che non stò dicendo che ho ragione per forza, ma che stò solo ragionando in un certo modo.

La funzione di complessità dipende da n perchè anche per n < 44 i cicli vengono eseguiti.

Per il fatto del limite superiore quello che dici è naturale per il semplice fatto che la funzione di complessità di un algoritmo è, per definizione, una funzione monotona non decrescente.

Tu stai scegliendo un valore n preciso, chiamiamolo k (nel nostro caso sarebbe il valore 44), e dici che per ogni n < 44, f(n) (chiamiamo f la nostra funzione di complessità) <= f(k). Ma questo, come vedi, non dice nulla sulla natura della funzione f(n), anzi, lo potresti fare per qualsiasi valore k (visto che f è monotona non decrescente).

[zzi_miei]

ma neanche io voglio avere ragione per forza...penso che stiamo discutendo normalmente

detto questo, la costante cui mi riferisco non e' n=44 ma la costante che usi nella definizione di O-grande (io sono abituato a chiamarla c). per come la vedo tra 0 e 44 non importa tanto come va la funzione poiche' la si puo' approsimare con un valore costante,cosa che non si puo' fare per tutti gli n successivi.

[BlackICE]

Si infatti... era il dubbio iniziale che avevo. Cioè, non mi sembrava molto sensato parlare di complessità asintotica per n limitato. Come dici te, basterebbe fissare la costante c abbastanza grande e il gioco è fatto.

Nel mio caso facevo una specie di interpolazione prendendo il comportamento della complessità dell'algoritmo per n compreso tra 10 e 44 e generalizzandolo come una funzione su tutto il dominio dei naturali.

A conti fatti, anzi, a definizioni fatte :P, direi che non ha semplicemente senso parlare di complessità asintotica per intervalli finiti di n. In effetti anche la definizione di "O grande" rende insensato parlare di complessità asintotica per intervalli finiti di n.

A questo punto direi semplicemente che la complessità asintotica, nel caso pessimo, dell'algoritmo è O(n^3).

Complimenti @zzi_miei comunque: questo è il modo di portare avanti discussioni in maniera costruttiva. Se ne impara tuttti qualcosa.

See you.

[zzi_miei]

bhe...speriamo che ce ne possano essere altre.

:P