Big-O: cât de repede crește timpul
La fiecare interviu ți se pune aceeași întrebare: „Care este complexitatea soluției tale?”. Răspunsul se dă în notația Big-O, care spune cum crește numărul de pași al unui algoritm când datele cresc. Azi înveți primele două clase: O(1) și O(n).
De ce nu măsurăm în secunde
Același program rulează în 0,1 secunde pe un laptop nou și în 0,5 secunde pe unul vechi. Secundele depind de calculator, de limbaj, chiar și de ce alte programe sunt deschise. De aceea informaticienii numără altceva: câți pași face algoritmul în funcție de mărimea datelor, notată cu n.
Scrie funcția pasi_suma(n) care parcurge cu o buclă numerele de la 1 la n, le adună și numără câte adunări a făcut. Funcția returnează numărul de adunări. Testele afișează rezultatul ca 10 -> 10.
- Creează un total și un contor pasi, ambele 0.
- Parcurge range(1, n + 1): adună numărul la total și crește contorul cu 1.
- Returnează contorul. Rezultatele trebuie să fie 1, 10, 100 și 1000.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Primii pași, tablouri, two pointers și sliding window.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan