Examen DL Informatica Unibuc

Buna seara! Uitandu-ma peste subiectele date in anii precedenti am vazut ca se cere calcularea complexitatii in timp a programului. Ar putea sa-mi explice cineva cum se rezolva aceasta cerinta?

incepe si tu de aici si apoi mai citesti: https://en.wikipedia.../Big_O_notation

Cam toate cartile de algoritmi trateaza problema.
Celebra Introduction to Algorithms iti zice si ce inseamna complexitatea asta si o mentioneaza valorile si la fiecare algoritm prezentat (adesea si doveste de ce-i asa, nu doar tranteste valoarea).

Pe scurt, te gandesti cum ar evolua numarul de operatiuni executate pe masura ce ai seturi de date mai mari.

Exemplu: daca ai un vector de numere si vrei sa cauti daca exista valoarea 1234 in el, trebuie sa cauti iei fiecare valoare la rand si s-o compari cu 1234. Ai deci o evolutie liniara (n). Daca ai 5 elemente in vector, executi de 5x un anumit numar de operatii, daca ai 100.000 elemente, executi 100.000 de astfel de operatii.

Alti algoritmi pot fi mai rapizi daca ai valorile gata ordonate. De exemplu sa cauti 1234 in 100.000 valori ordonate iei valoarea din mijloc si o compari cu 1234. Daca la mijloc e valoarea 56774 stii ca sigur 1234, daca exista in vector, il vei gasi in jumatatea stanga (valori < 56774), asadar scapi de verificat 50.000 valori din jumatatea dreapta. Repetand asta, constati ca ai nevoie de mult mai putine comparatii pana dai de 1234. Mai exact log2(n) in cel mai rau caz, adica vreo 17. Infinit mai putine decat 100.000.


Programul din semnatura te poate ajuta sa vezi aflii practic evolutia pentru programe scrise de tine, in caz ca nu observi matematic.

Edited by dani.user, 24 September 2016 - 20:43.