[canonical]: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-036

> Pagina completă: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-036
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model Preadmitere Politehnica București · Informatică #036

10 grile din Complexitate, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul Preadmitere Politehnica București

## Teaser gratuit, fără cont

1. Care este complexitatea temporală a secvenței de mai jos, în funcție de `n`?

a) $O(n)$
b) $O(n^3)$
c) $O(2^n)$
d) $O(n\log n)$
e) $O(n^2)$

Răspuns corect: e) $O(n^2)$

Bucla interioară face $i$ pași, deci în total $0+1+\dots+(n-1)=\frac{n(n-1)}{2}$ incrementări — pătratic în $n$; constanta $\frac12$ nu contează în notația $O$.

2. Vectorul `v`, cu `n` elemente, este sortat crescător. Care este complexitatea temporală, în cazul cel mai defavorabil, a secvenței de mai jos?

a) $O(n^2)$
b) $O(n\log n)$
c) $O(n)$
d) $O(\log n)$
e) $O(1)$

Răspuns corect: c) $O(n)$

Oprirea la primul element $\ge x$ ajută doar în medie; dacă `x` este mai mare decât toate elementele, bucla parcurge tot vectorul. Faptul că vectorul este sortat nu aduce $O(\log n)$ decât dacă se înjumătățește intervalul.

3. Ce se afișează în urma executării secvenței de mai jos, pentru $n=10$?

a) $45$
b) $100$
c) $55$
d) $50$
e) $10$

Răspuns corect: c) $55$

`break` oprește bucla interioară de îndată ce $j>i$, deci pentru fiecare `i` se numără $i+1$ pași: $1+2+\dots+10=55$.

4. Care este complexitatea temporală a secvenței de mai jos, în funcție de `n`?

a) $O(n)$
b) $O(n\log n)$
c) $O(n^2)$
d) $O(2^n)$
e) $O(\log n)$

Răspuns corect: b) $O(n\log n)$

`i` se dublează, deci bucla exterioară se execută de $\lfloor\log_2 n\rfloor+1$ ori, iar pentru fiecare `i` bucla interioară face $n$ pași: $n\cdot(\log_2 n+1)$.

5. Secvența de mai jos simulează căutarea binară a valorii `x` într-un vector sortat cu un milion de elemente, în care $v[i]=i$ pentru $i=0,1,\dots,n-1$ (de aceea, în cod, `m` joacă rolul lui `v[m]`). Ce se afișează?

a) $1000000$
b) $20$
c) $19$
d) $21$
e) $500000$

Răspuns corect: b) $20$

$x=10^6$ este mai mare decât toate elementele ($0\dots999999$), deci la fiecare pas se păstrează jumătatea dreaptă: intervalul are $10^6, 5\cdot10^5, \dots, 1$ elemente și devine vid după $\lfloor\log_2 10^6\rfloor+1=20$ iterații ($2^{19}<10^6<2^{20}$).