Time Limit Exceeded: x in lista într-o buclă face soluția O(n²)
x in lista caută element cu element (O(n)), iar într-o buclă peste n elemente devine O(n²): pe date mari programul depășește limita de timp. Transformă lista în set o singură dată (set_b = set(b)), apoi x in set_b e O(1) în medie.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Programul e corect, dar prea lent: pe exemplele mici merge, iar pe datele mari e oprit după limita de timp (pe platformele de probleme: Time Limit Exceeded, în editorul nostru: „programul a rulat prea mult”).
Cauza clasică: if x in lista în interiorul unui for. Pentru o listă, in verifică elementele unul câte unul, deci costă O(n). Repetat de n ori, ajungi la O(n²): pentru 50.000 de elemente, de ordinul a miliarde de comparații. Aceeași capcană au lista.index(x), lista.count(x), lista.remove(x) și lista.pop(0) în buclă.
Un set sau un dict folosesc o tabelă hash: x in s calculează direct unde ar trebui să fie x, deci costă O(1) în medie. Construirea set-ului e O(n), o singură dată, iar soluția devine O(n).
De ce apare: cauzele frecvente
1Căutare în listă pentru fiecare element
comune = 0
for x in a:
if x in b:
comune += 1set_b = set(b)
comune = 0
for x in a:
if x in set_b:
comune += 1set(b) se construiește o dată, apoi fiecare in e O(1).
2Set-ul construit în interiorul buclei
for x in a:
if x in set(b):
comune += 1set_b = set(b)
for x in a:
if x in set_b:
comune += 1set(b) în buclă reconstruiește set-ul la fiecare pas (O(n) de fiecare dată), deci soluția rămâne O(n²).
3count în buclă pentru frecvențe
for x in nums:
if nums.count(x) > 1:
duplicate.add(x)from collections import Counter
frecv = Counter(nums)
duplicate = {x for x, c in frecv.items() if c > 1}Counter numără totul într-o singură trecere, O(n).
Repară eroarea, direct în pagină
Funcția clienti_comuni(a, b) numără clienții care apar în ambele liste (fiecare listă are 50.000 de coduri distincte). Codul e corect, dar e oprit după limita de timp. Fă-l rapid, ca să afișeze 16667.
def clienti_comuni(a, b):
comune = 0
for cod in a:
if cod in b:
comune += 1
return comune
a = list(range(0, 100000, 2))
b = list(range(0, 150000, 3))
print(clienti_comuni(a, b))16667
Indiciu
Transformă lista b într-un set o singură dată, înainte de buclă.
Reparația
def clienti_comuni(a, b):
set_b = set(b)
comune = 0
for cod in a:
if cod in set_b:
comune += 1
return comune
a = list(range(0, 100000, 2))
b = list(range(0, 150000, 3))
print(clienti_comuni(a, b))De ce merge
Cu cod in b pe o listă, fiecare verificare parcurgea până la 50.000 de elemente, iar bucla le repeta de 50.000 de ori: peste un miliard de comparații. set(b) se construiește o singură dată, în O(n), iar apoi cod in set_b e O(1) în medie, deci totalul e O(n). Codurile comune sunt multiplii de 6 sub 100.000, adică 16.667.
Alte forme ale mesajului
Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.Time Limit Exceeded
Cum o eviți pe viitor
Înainte să trimiți o soluție, estimează complexitatea: câte bucle sunt una în alta și ce costă operațiile din ele. Ține minte costurile ascunse: in, index, count, remove și pop(0) pe liste sunt O(n). Când verifici apartenența în buclă, folosește set; când numeri, dict sau Counter; pentru coadă, deque. Testează și pe un caz mare generat (list(range(100000))), nu doar pe exemple.
Întrebări frecvente
De ce merge pe exemple, dar nu la testele mari?
La 10 elemente, O(n²) înseamnă 100 de pași, instant. La 100.000 de elemente înseamnă de ordinul 10 miliarde de pași, adică minute sau ore.
Set-ul folosește mai multă memorie. Merită?
Aproape mereu. Memoria crește cu O(n), iar timpul scade de la O(n²) la O(n). Pe datele din probleme, diferența e de la ore la milisecunde.
Erori înrudite
AttributeError: 'set' object has no attribute 'append' Un set nu are append, pentru că nu are ordine sau poziții. Elementele se adaugă cu add(x), iar mai multe deodată cu update(lista). Pe dos, la o listă se folosește append, nu add. Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină Funcția recursivă recalculează aceleași subprobleme de un număr exponențial de ori (fib(40) face sute de milioane de apeluri), așa că pare blocată și editorul o oprește după limita de timp. Salvează rezultatele: @lru_cache(maxsize=None) sau un dicționar memo. ValueError: list.remove(x): x not in list Ai cerut ștergerea unei valori care nu (mai) e în listă: lista.remove(x) caută valoarea, nu poziția, și aruncă eroare dacă nu o găsește. Verifică înainte cu if x in lista sau folosește un set / un Counter pentru elementele disponibile. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
