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…
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.
Observă datele de pornire.
Urmărește ce se schimbă.
Verifică și explică rezultatul.
Lista crește
O căutare liniară poate verifica, în cel mai rău caz, toate cele 4 nume.
PARTEA 1
Cum crește timpul de executare
Aceeași sumă, două strategii
- 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
- 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.
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:
Alege un răspuns.
Dacă două bucle de n pași sunt imbricate, operația interioară se execută de câte ori?
Alege un răspuns.
Observă · urmărește · încearcă
Cum crește munca?
Compară numărul de repetări, nu viteza unui anumit calculator.
Numărăm operația dominantă într-un model simplificat.
Dublarea lui n dublează modelul liniar și înmulțește cu 4 modelul pătratic.
Diferența de creștere devine tot mai vizibilă.
Aceste concluzii presupun n pași pentru fiecare buclă și cost constant al operației urmărite.
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
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
- 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ție | Timp în modelul simplu | Spațiu auxiliar |
|---|---|---|
| Sumă printr-o buclă | O(n) | O(1) |
| Sumă prin formula matematică | O(1) | O(1) |
| Construirea unei liste cu n valori | O(n) | O(n) |
| Parcurgerea unei liste deja existente, cu un contor | O(n) | O(1), fără a număra lista de intrare |
- 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?
Alege un răspuns.
Care este primul criteriu înaintea optimizării?
Alege un răspuns.
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())2s = n * (n + 1) // 23print(s)Variabile după pas
| Nume | Valoare | Tip |
|---|---|---|
| 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.
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ă
- 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