Analiza complexității unui algoritm
Ideile de bază pe scurt și, unde există, exercițiile din subiectele de BAC care le verifică. Lecția completă, animată, cu grile și exerciții corectate, e în aplicația Tomomi.
Pe scurt
Șablon: câți pași face o secvență
Numeri pașii în funcție de n, nu în secunde:
for (i = 0; i < n; i++) // n pași
for (i...) for (j...) // n · n pași (imbricate)
for (i...) ; for (j...) // n + n pași (succesive)
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++) // n(n-1)/2 pași
Capcana: imbricat înmulțește, succesiv adună
Două bucle una în alta fac n · n pași; două bucle una DUPĂ alta fac n + n. Este cea mai frecventă confuzie din capitol: uită-te dacă a doua buclă se află în CORPUL primeia sau după ea.
Cele patru etichete
Ce se întâmplă când dublezi n:
O(1) // nimic nu se schimbă
O(log n) // un singur pas în plus (căutare binară)
O(n) // de două ori mai mulți (parcurgere, căutare secvențială)
O(n²) // de patru ori mai mulți (bule, selecție)
Idee: eticheta ignoră constantele
n, 2n și n + 10 sunt toate O(n): eticheta descrie ordinul de creștere, nu numărul exact de pași. La fel, n(n+1)/2 este O(n²), chiar dacă face cam jumătate din pașii unei bucle imbricate pline.
Memoria suplimentară a algoritmilor cunoscuți
Peste datele de intrare, fiecare algoritm mai cere:
metoda bulelor / selecția // câteva variabile (pe loc)
căutarea secvențială/binară // câteva variabile (pe loc)
sortarea prin numărare // tablou de frecvență, cât domeniul valorilor
interclasarea // un al treilea vector, n + m celule
Idee: compromisul timp-memorie
Sortarea prin numărare este mult mai rapidă decât metoda bulelor, dar plătește cu un tablou suplimentar. Când compari doi algoritmi care rezolvă aceeași problemă, îi compari după AMBELE criterii din programă: durata de executare și spațiul de memorie.
Din subiectele de BAC
Exerciții reale din subiectele anilor trecuți. Încearcă-le singur înainte să deschizi rezolvarea.
Un tânăr pasionat de călătorii are o listă cu muzee virtuale și, pentru fiecare, câte un singur interval orar, în care acesta poate fi vizitat online, gratuit. Tânărul dispune zilnic de același interval orar pentru vizite; un muzeu este convenabil dacă poate fi vizitat online gratuit în timpul disponibil și dacă pentru vizită îi poate aloca cel puțin o oră. Muzeele din listă sunt numerotate cu valori naturale consecutive, începând cu 1, și cel puțin unul este convenabil.
Fișierul text bac.in conține cel mult linii, iar pe fiecare linie câte o pereche de numere, reprezentând limitele câte unui interval orar: pe prima linie intervalul orar de care tânărul dispune zilnic, iar pe fiecare dintre următoarele linii, intervalul orar de vizitare gratuită pentru câte un muzeu, în ordinea din listă. Limitele intervalelor sunt ore fixe, numere naturale din intervalul , iar cele aflate pe aceeași linie a fișierului sunt în ordine strict crescătoare și sunt separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori, reprezentând numărul de muzee convenabile, respectiv numărul de ordine al ultimului astfel de muzeu din lista tânărului. Utilizați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține valorile 16 19, 15 18, 17 21, 19 21, 18 20, 12 13, atunci pe ecran se afișează numerele 3 4 (pot fi vizitate trei muzee cu numerele de ordine 1, 2 și 4, în intervalele 16-18, 17-19, respectiv 18-19).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Vezi rezolvarea
Citim prima pereche - intervalul de care dispune tânărul - și apoi, pe măsură ce citim fiecare dintre perechile următoare , îi calculăm intersecția cu intervalul disponibil:
Dacă , adică intersecția conține cel puțin o oră, incrementăm contorul de muzee convenabile și reținem numărul de ordine curent ca fiind al ultimului muzeu convenabil. La final afișăm contorul și acest număr de ordine.
Eficiența: fiecare linie a fișierului este citită și prelucrată o singură dată, deci timpul de executare este liniar în numărul de muzee, - minimul posibil, pentru că orice soluție trebuie măcar să citească datele. Memoria folosită este constantă, : nu se rețin intervalele citite într-un tablou, ci doar intervalul disponibil, contorul, numărul de ordine curent și cel al ultimului muzeu convenabil. Cum fișierul poate avea până la linii, evitarea tabloului este exact ceea ce se cere prin „eficient din punctul de vedere al memoriei utilizate".
De-a lungul unui traseu montan este utilizată o succesiune de marcaje turistice, care trebuie urmate în acea ordine. Pentru fiecare marcaj se cunoaște cota (înălțimea, măsurată în metri) la care este plasat. Numim scară într-un traseu o secvență de marcaje aflate pe poziții consecutive în cadrul traseului, care au drept cote numere consecutive, ordonate strict crescător. O scară este formată din cel puțin două marcaje, iar lungimea acesteia este egală cu numărul de marcaje care o compun.
Fișierul bac.txt conține un șir de cel mult numere naturale din intervalul , separate prin câte un spațiu, reprezentând cotele marcajelor turistice din cadrul unui traseu, în ordinea în care se succed în acesta. Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict crescătoare, cotele corespunzătoare marcajelor unei scări de lungime maximă pe acest traseu. Dacă există mai multe astfel de scări, se afișează cotele uneia dintre ele, iar dacă nu există nicio scară, se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 500 600 601 405 569 570 700 701 625 626 627 520, atunci pe ecran se afișează 625 626 627.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Vezi rezolvarea
Algoritm: parcurgem fișierul o singură dată. Păstrăm pentru scara curentă lungimea lgCrt și ultima cotă ultCrt, iar pentru cea mai lungă scară găsită lungimea lgMax și ultima sa cotă ultMax. Pentru fiecare număr x citit: dacă x = ultCrt + 1, scara curentă continuă (lgCrt crește cu 1); altfel începe o scară nouă (lgCrt = 1). După fiecare pas actualizăm ultCrt = x, iar dacă lgCrt > lgMax reținem lgMax = lgCrt și ultMax = x. La final, dacă lgMax < 2 nu există nicio scară și afișăm mesajul cerut; altfel afișăm numerele consecutive de la ultMax - lgMax + 1 până la ultMax.
Eficiență: timpul este liniar, O(n), fișierul fiind parcurs o singură dată, iar memoria este constantă, O(1): nu memorăm șirul (care poate avea elemente), ci doar câteva variabile simple, scara afișată fiind reconstituită din ultima cotă și lungime.
Un număr natural x este numit prefix al unui număr natural y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la dreapta sa, și este numit sufix al lui y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la stânga sa.
Exemplu: 15 este prefix pentru 154 sau 1521, este sufix pentru 3415 sau 5115, dar nu este nici prefix, nici sufix pentru 15.
Fișierul bac.txt conține maximum numere naturale din intervalul , separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix, respectiv ca prefix al numerelor din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul 342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310 se afișează pe ecran: 4 (pentru valorile 10, 11, 16, 34).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Vezi rezolvarea
Algoritm: Folosim doi vectori de frecvență cu indici de la 10 la 99: pf[v] numără de câte ori apare v ca prefix, iar sf[v] de câte ori apare ca sufix. Citim numerele din fișier unul câte unul, fără a le memora. Numerele de două cifre nu produc nici prefix, nici sufix de două cifre (ar trebui eliminată cel puțin o cifră). Pentru fiecare număr x cu : sufixul de două cifre este (numărat doar dacă este cel puțin 10), iar prefixul de două cifre este dacă x are trei cifre, respectiv dacă are patru cifre. La final numărăm valorile cu pf[v] = sf[v] și sf[v] nenul.
Eficiență: fișierul este parcurs o singură dată, deci timpul este liniar, pentru numere; memoria este constantă, două tablouri de cel mult 100 de elemente, fără a memora șirul de numere.