INFORMATICĂ · CLASA A IX-A

Eficiența algoritmilor

Două soluții pot da același rezultat și totuși să consume resurse diferite. Comparăm creșterea numărului de pași și a memoriei.

Distribuie

Trimite pe…

Teme / Exerciții ↓
Observă · Din viața reală

Căutăm un nume pe lista participanților

Situația și ce ai de aflat

O căutare liniară poate verifica, în cel mai rău caz, toate cele 4 nume.

Ce se schimbă în numărul maxim de verificări când lista crește de la 4 la 8 nume?

Legătura cu lecția: Complexitatea descrie cum crește munca odată cu numărul datelor, în condițiile modelului ales.

1Lista crește

Observă datele de pornire.

2Lista se dublează

Urmărește ce se schimbă.

3Comparăm toate perechile

Verifică și explică rezultatul.

Lista crește

O căutare liniară poate verifica, în cel mai rău caz, toate cele 4 nume.

4Etapa 1 · Lista crește

PARTEA 1

Cum crește timpul de executare

Aceeași sumă, două strategii

Pe scurt
  • Aceeași sumă: adunări repetate sau formulă.
  • Compară numărul de operații pentru aceeași intrare.

Python

n = int(input("n = "))
suma = 0
for i in range(1, n + 1):
    suma += i
print(suma)

Python

n = int(input("n = "))
suma = n * (n + 1) // 2
print(suma)
Explicația pe larg

Manualul compară suma numerelor 1 + 2 + … + n, calculată prin adunări succesive, cu formula n × (n + 1) / 2. Pentru n = 5, ambele produc 15. Prima soluție adună cinci valori; a doua folosește aceeași expresie indiferent de n. Diferența devine importantă atunci când n crește.

Notația O descrie creșterea

Pe scurt
  • O(1): număr de pași limitat; O(n): crește cu n.
  • O(n²): creștere mult mai rapidă pentru date mari.

O(1) · constant

Un număr fix de operații, precum formula sumei în modelul folosit aici. Nu înseamnă neapărat o singură instrucțiune.

O(log n) · logaritmic

Dimensiunea este redusă repetat cu un factor, de exemplu prin înjumătățire până la 1.

O(n) · liniar

O parcurgere completă a n valori. Dacă dublăm n, numărul pașilor principali se dublează aproximativ.

O(n²) · pătratic

Două bucle imbricate, fiecare cu n pași, produc n × n execuții ale operației din interior.

De ce O(1) nu înseamnă timp identic pe orice calculator?

Notația descrie dependența de dimensiunea intrării în modelul analizat. Procesorul, implementarea și alte costuri influențează timpul efectiv. Pentru întregi foarte mari, costul operațiilor numerice necesită o analiză mai fină.

Explicația pe larg

În analiza introductivă, tratăm operațiile aritmetice elementare ca având cost constant. Numărăm o operație reprezentativă și observăm cum depinde numărul ei de dimensiunea n. Notația O exprimă o limită de creștere; nu este o durată în secunde. Constantele și termenii de ordin mai mic nu schimbă clasa uzuală de complexitate.

Manualul prezintă și creșterea exponențială O(2ⁿ), ca reper pentru algoritmi care explorează combinații. La dublarea lui n, o expresie pătratică se multiplică aproximativ cu 4, nu cu 2. Două bucle succesive de n pași înseamnă aproximativ 2n, adică O(n), în timp ce buclele imbricate pot produce n².

Compară modele de creștere

Schimbă n și compară operațiile numărate. Valorile afișate sunt un model didactic, nu o măsurare a performanței browserului.

Anticipează rezultatul, apoi încearcă.

Simulator pentru exemplul acestei lecții; nu execută cod Python arbitrar. Datele rămân în această pagină.

Recunoaște modelul

Două bucle succesive cu n pași fiecare au, în modelul simplu, creștere:

Dacă două bucle de n pași sunt imbricate, operația interioară se execută de câte ori?

Observă · urmărește · încearcă

Cum crește munca?

Compară numărul de repetări, nu viteza unui anumit calculator.

Harta vizuală: Cum crește munca?
1
n = 2

Numărăm operația dominantă într-un model simplificat.

constant1
liniar2
pătratic4
2
n = 4

Dublarea lui n dublează modelul liniar și înmulțește cu 4 modelul pătratic.

constant1
liniar4
pătratic16
3
n = 8

Diferența de creștere devine tot mai vizibilă.

constant1
liniar8
pătratic64
4
Interpretăm

Aceste concluzii presupun n pași pentru fiecare buclă și cost constant al operației urmărite.

două bucle succesive2n → O(n)
două bucle imbricaten² → O(n²)

Privește → anticipează → explică. Acoperă exemplul, spune ce se întâmplă și descoperă-l pentru verificare. Apoi folosește demonstrația de mai jos pentru a urmări schimbările.

Vezi cum se întâmplă

Alege un pas sau pornește demonstrația. Te poți opri oricând pentru explicații.

n = 2

constant1
liniar2
pătratic4

Numărăm operația dominantă într-un model simplificat.

Acum anticipează tu

În acest model, când n trece de la 8 la 16, n² trece de la 64 la:

Alege, apoi citește explicația.

La tablă: oprește înaintea unui pas, cere o predicție și discută ce s-a schimbat și ce a rămas la fel.

PARTEA 2

Memorie și alegerea unei soluții

Complexitatea memoriei

Pe scurt
  • Urmărește spațiul suplimentar folosit de algoritm.
  • Câteva variabile și o listă de n valori au costuri diferite.

O(1) · câteva variabile

Pentru suma 1 + … + n păstrăm n, i și suma. Numărul variabilelor nu crește cu n, în modelul introductiv.

O(n) · toate valorile

O listă cu n elemente necesită spațiu proporțional cu n. Memorarea este utilă dacă vom reveni la elemente.

Explicația pe larg

Pe lângă timp, contează memoria suplimentară folosită de algoritm. Dacă însumăm valori pe măsură ce le citim, sunt suficiente câteva variabile, indiferent câte valori procesăm. Dacă memorăm toate valorile într-o listă, ocuparea memoriei crește odată cu numărul lor. Trebuie precizat dacă analizăm memoria totală sau memoria auxiliară; în această lecție urmărim memoria suplimentară, ca în explicația manualului.

Cum estimăm corect?

SituațieTimp în modelul simpluSpațiu auxiliar
Sumă printr-o buclăO(n)O(1)
Sumă prin formula matematicăO(1)O(1)
Construirea unei liste cu n valoriO(n)O(n)
Parcurgerea unei liste deja existente, cu un contorO(n)O(1), fără a număra lista de intrare
Pe scurt
  • Numără pașii dominanți și observă buclele imbricate.
  • Timpul măsurat pe un singur calculator nu este complexitatea.
Înjumătățirea lui n are n pași?

Nu. Pentru n = 16, valorile devin 8, 4, 2, 1: patru pași. Numărul lor este logaritmic. Când n se dublează, se adaugă aproximativ un singur pas.

Explicația pe larg

Pentru o buclă, estimăm numărul de iterații și costul corpului. Pentru instrucțiuni succesive, adunăm costurile; pentru repetări imbricate, analizăm de câte ori ajunge să ruleze operația relevantă. Dacă limitele interioare variază, nu presupunem automat n² fără să verificăm.

Corectitudine, claritate, apoi optimizare

O soluție rapidă, dar greșită, nu rezolvă problema. Verificăm întâi corectitudinea, apoi dacă resursele consumate sunt potrivite dimensiunii datelor. Pentru date mici, lizibilitatea și simplitatea pot conta mai mult decât o diferență minoră de timp. Pentru date mari, o clasă de complexitate nepotrivită poate face soluția inutilizabilă.

O cronometrare izolată nu explică singură eficiența. Repetă măsurările în condiții comparabile, păstrează aceleași date și observă tendința pe mai multe dimensiuni. Nu confunda numărul de linii de cod cu numărul operațiilor executate. Un singur rând poate declanșa o prelucrare complexă.

O soluție folosește trei variabile indiferent de n. Cum descriem spațiul auxiliar în modelul lecției?

Care este primul criteriu înaintea optimizării?

Observă · Tu alegi datele, tu controlezi pașii

Execută și urmărește programul

Schimbă valorile, pregătește execuția și avansează câte o instrucțiune. Linia evidențiată este cea tocmai executată; variabilele și ieșirea arată starea de după acel pas.

Pregătește datele pentru execuție.

Program Python

n = int(input())s = n * (n + 1) // 2print(s)

Variabile după pas

NumeValoareTip
Nicio atribuire încă.

Ieșire

Nicio afișare încă.

Compară cu parcurgerea din lecția despre bucle. Aici numărăm instrucțiunile modelului, fără a măsura timpul procesorului.

Atelierul reproduce execuția programului afișat, pentru datele acceptate de câmpuri. Nu execută cod Python introdus liber și nu accesează fișierele dispozitivului. Poți copia programul într-un mediu Python pentru a compara rezultatele.

Exersează

Pune blocurile de cod în ordine

Citește n, număr natural. Afișează suma primelor n numere naturale nenule folosind formula n * (n + 1) // 2.

Alege blocurile în ordinea dorită. În soluție, folosește săgețile pentru a le muta. Blocurile nu se modifică în timpul jocului.

Blocuri de ales

Soluția ta

Alege primul bloc din zona de alături.

    Începe prin alegerea datelor sau a scopului.

    Compară cu modelul
    n = int(input())
    s = n * (n + 1) // 2
    print(s)

    Datele și inițializările trebuie pregătite înaintea prelucrării; afișarea folosește rezultatele calculate. Blocurile indentate rămân împreună. Comparăm cu programul-model; alte soluții pot fi corecte.

    Teme / Exerciții

    1 · Creștere

    Compară n și n² pentru n = 10, 100 și 1000. Explică de ce diferența dintre două soluții se poate mări rapid.

    Indiciu / verificare

    Valorile n² sunt 100, 10000 și 1000000. Dacă n se multiplică cu 10, costul pătratic se multiplică cu 100.

    2 · Timp și memorie

    Pentru media a n temperaturi, când poți evita memorarea tuturor valorilor? Când ar fi utilă lista?

    Indiciu / verificare

    Pentru o singură sumă și un număr de valori poți procesa pe rând. Dacă trebuie să sortezi sau să compari ulterior fiecare valoare cu media, memorarea poate fi utilă.

    3 · Justifică o alegere

    Scrie suma 1 + … + n cu buclă și cu formulă. Testează n = 0, 1, 10. Explică rezultatul și complexitatea fiecărei soluții.

    Indiciu / verificare

    Ambele dau 0, 1 și 55. Bucla este liniară, formula constantă în modelul operațiilor elementare cu cost constant.

    Alege nivelul de antrenament

    Basic consolidează ideea, Mediu combină pașii, iar Avansat cere justificări și cazuri-limită. Profesorul poate selecta sarcinile; nu este necesar să rezolvi toate nivelurile într-o singură temă. Exercițiile de mai sus sunt păstrate; acestea sunt propuneri originale suplimentare.

    Basic

    1 · Număr de pași

    O buclă execută o adunare pentru fiecare i din range(n). Câte adunări face pentru n=5 și n=10?

    Reper de verificare

    5 și 10; model liniar.

    2 · Formula

    Calculează suma 1…n prin formulă pentru n=8 și compară rezultatul cu bucla.

    Reper de verificare

    36 în ambele variante.

    Mediu

    1 · Succesiv sau imbricat

    Compară două bucle succesive de n pași cu două bucle imbricate de n pași.

    Reper de verificare

    2n față de n² în modelul dat; pentru n=4:8 și 16.

    2 · Memorie

    Compară citirea și însumarea imediată cu păstrarea tuturor celor n valori într-o listă.

    Reper de verificare

    Spațiu auxiliar O(1), respectiv O(n), în modelul lecției.

    Avansat

    1 · Dublare

    Pentru modelele n, n² și n log₂n, construiește un tabel la n=4,8,16. Explică ce compari.

    Reper de verificare

    Nu transforma numerele-model în secunde măsurate.

    2 · Alegere argumentată

    Propune două soluții corecte pentru aceeași sumă și justifică alegerea prin corectitudine, claritate și creșterea muncii.

    Reper de verificare

    Precizează ipotezele despre costul operațiilor.

    Pentru predare: trimite codul sau pașii soluției, minimum două teste și o explicație a rezultatului. Pentru probleme conceptuale, predă schema și justificarea.

    Privește, oprește și explică

    Tutoriale video din manualele digitale CD PRESS. Alege manualul specializării tale. Videoclipul se încarcă la cerere, de la sursa originală. Explicațiile scrise și exemplele lecției permit și studiul fără sunet.

    ▶ Matematică-informatică · Eficiența algoritmilor

    Ce să urmărești: Compară operațiile efectuate pentru aceeași problemă. Distinge modelul de numărare de o măsurare a timpului real.

    © Editura CD PRESS · Manualul digital Matematică-informatică. Dacă playerul nu funcționează, deschide manualul și alege „Activități digitale animate” → „Eficiența algoritmilor”.

    ▶ Științe ale naturii · Eficiența algoritmilor

    Ce să urmărești: Compară operațiile efectuate pentru aceeași problemă. Distinge modelul de numărare de o măsurare a timpului real.

    © Editura CD PRESS · Manualul digital Științe ale naturii. Dacă playerul nu funcționează, deschide manualul și alege „Activități digitale animate” → „Eficiența algoritmilor”.

    Reține și explică

    Reține · recapitulare
    • Eficiența privește timpul și memoria în funcție de dimensiunea intrării.
    • O(1), O(log n), O(n) și O(n²) descriu modele diferite de creștere.
    • Analiza folosește un model de cost explicit și nu înlocuiește verificarea corectitudinii.
    Repere pentru profesor

    Repere: MI pp. 28–31; SN pp. 23–25. Explică diferența dintre numărătoare, ordin de creștere și durată măsurată. Modelul aritmetic cu cost constant este o simplificare potrivită începutului; nu formula garanții absolute despre timpi reali.

    Continuă parcursul

    Matematică-informatică

    Științe ale naturii

    Hub educațional digital pentru Informatică și TIC (Liceu) ClauAcademy

    Conceput conform programei școlare de informatică pentru anul 2026.

    Explicații și activități originale ClauAcademy, cu repere din manualele CD PRESS furnizate pentru clasa a IX-a, ediții de consultare 2026. Materialele de aici pot fi folosite independent; manualele sunt repere suplimentare.

    Termeni pe înțelesul tău

    Complexitate de timp
    Modul în care costul de executare depinde de dimensiunea datelor.
    Complexitate de memorie
    Modul în care spațiul necesar depinde de dimensiunea datelor.
    Dimensiunea intrării
    Mărimea n față de care analizăm creșterea costului.
    Operație elementară
    Operație tratată ca având cost fix în modelul ales.
    Spațiu auxiliar
    Memorie suplimentară față de datele de intrare.
    Optimizare
    Îmbunătățirea consumului de resurse, păstrând corectitudinea.