...
Eroare Algoritmi și structuri de date · Dicționare și set-uri

Time Limit Exceeded: x in lista într-o buclă face soluția O(n²)

Pe scurt

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

Greșit
PYTHON
comune = 0
for x in a:
    if x in b:
        comune += 1
Corect
PYTHON
set_b = set(b)
comune = 0
for x in a:
    if x in set_b:
        comune += 1

set(b) se construiește o dată, apoi fiecare in e O(1).

2Set-ul construit în interiorul buclei

Greșit
PYTHON
for x in a:
    if x in set(b):
        comune += 1
Corect
PYTHON
set_b = set(b)
for x in a:
    if x in set_b:
        comune += 1

set(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

Greșit
PYTHON
for x in nums:
    if nums.count(x) > 1:
        duplicate.add(x)
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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))
După reparație, programul afișează
16667
Indiciu

Transformă lista b într-un set o singură dată, înainte de buclă.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.