Lectia 6: Tehnici de optimizare | Clasa a XII-a Mat-Info

1

1. De ce optimizam? — costul alegerii gresite

O tehnica de optimizare reduce complexitatea timpului sau spatiului unui algoritm prin exploatarea structurii problemei. Alegerea gresita a algoritmului sau structurii de date transforma un program corect intr-unul inutilizabil pentru date mari.

Exemplu concret — Fibonacci naiv vs memoizat:

Fibonacci fara memoizare recalculeaza aceleasi valori de milioane de ori. fib(40) face ~330 de milioane de apeluri recursive. Cu memoizare: exact 40 de apeluri.

Tabel comparativ complexitate pentru probleme tipice:

Tehnica	Problema tipica	Naiv	Optimizat
Memoizare	Fibonacci, DP pe recursie	O(2ⁿ)	O(n)
Sume prefix	Suma interval [l, r]	O(n) per interogare	O(1) per interogare
Fereastra glisanta	Max/Min subarray fix k	O(n*k)	O(n)
Doi pointeri	Subarray cu suma data	O(n²)	O(n)
Hash map	Cautare/insertie frecventa	O(n) per op	O(1) amortizat

2

2. Memoizare — evitarea recalcularii

Memoizarea este tehnica de a stoca rezultatele apelurilor de functie intr-un dictionar (sau tablou), astfel incat apeluri viitoare cu aceiasi parametri sa returneze imediat valoarea stocata, fara a reparcurge recursiv arborele.

Fibonacci fara memoizare (Python), verificat:

# Fibonacci cu memoizare — dict cache
memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

for i in [0, 1, 5, 10, 20, 40]:
    print(f"fib({i}) = {fib(i)}")

Output real (rulat cu python):

fib(0) = 0
fib(1) = 1
fib(5) = 5
fib(10) = 55
fib(20) = 6765
fib(40) = 102334155

⚡ EXCLUSIV INTENSIV — Memoizare in C++

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<long long, long long> memo;

long long fib(long long n) {
    if (n <= 1) return n;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    for (int n : {0, 1, 5, 10, 20, 40}) {
        cout << "fib(" << n << ") = " << fib(n) << endl;
    }
    return 0;
}

Output real (compilat g++ -std=c++17, apoi rulat):

fib(0) = 0
fib(1) = 1
fib(5) = 5
fib(10) = 55
fib(20) = 6765
fib(40) = 102334155

3

3. Precompute — sume prefix pentru interogari rapide

Sumele prefix (prefix sums) sunt un tablou auxiliar in care prefix[i] stocheaza suma primelor i elemente. Odata construit in O(n), orice interogare de suma pe interval [l, r] se raspunde in O(1).

Constructie si interogare (Python), verificat:

# Precompute prefix sums
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
n = len(arr)

# Construire O(n)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]

def query(l, r):
    # Suma arr[l..r] in O(1)
    return prefix[r+1] - prefix[l]

print("Array:", arr)
print("Prefix:", prefix)
print("Sum [2..5]:", query(2, 5))
print("Sum [0..3]:", query(0, 3))
print("Sum [6..9]:", query(6, 9))

Output real (rulat cu python):

Array: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
Prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31, 36, 39]
Sum [2..5]: 19
Sum [0..3]: 9
Sum [6..9]: 16

Verificare manuala Sum [2..5]: arr[2]+arr[3]+arr[4]+arr[5] = 4+1+5+9 = 19 ✓

Complexitate: constructie O(n), spatiu O(n), fiecare interogare O(1). Pentru q interogari: O(n + q) in loc de O(n * q).

4

4. Fereastra glisanta — subarray-uri de lungime fixa

Fereastra glisanta (sliding window) mentine o suma (sau alta proprietate) pentru o fereastra de lungime fixa k. La fiecare pas, fereastra se deplaseaza cu o pozitie: se scade elementul care iese din stanga si se adauga elementul nou din dreapta — O(1) per pas, O(n) total in loc de O(n*k).

Suma maxima a unui subarray de lungime k (Python), verificat:

# Sliding window: suma maxima subarray de lungime k
def max_sum_window(arr, k):
    n = len(arr)
    # Prima fereastra
    window_sum = sum(arr[:k])
    max_sum = window_sum
    max_start = 0
    # Deplasam fereastra
    for i in range(1, n - k + 1):
        window_sum = window_sum - arr[i-1] + arr[i+k-1]
        if window_sum > max_sum:
            max_sum = window_sum
            max_start = i
    return max_sum, max_start, arr[max_start:max_start+k]

arr = [2, 1, 5, 1, 3, 2, 4, 3, 1, 2]
k = 3
max_sum, start, window = max_sum_window(arr, k)
print("Array:", arr)
print(f"k = {k}")
print(f"Max sum window: {window} starting at index {start}")
print(f"Max sum: {max_sum}")

Output real (rulat cu python):

Array: [2, 1, 5, 1, 3, 2, 4, 3, 1, 2]
k = 3
Max sum window: [5, 1, 3] starting at index 2
Max sum: 9

Complexitate: O(n) timp, O(1) spatiu auxiliar (in afara de input). Varianta naiva cu doua cicluri ar fi O(n*k).

5

5. Doi pointeri — subarray cu suma data

Doi pointeri (two pointers) mentine doua pozitii left si right care delimiteaza un subarray. Pe siruri cu valori pozitive, extindem right cand suma e prea mica si avansam left cand suma e prea mare. Fiecare element este vizitat cel mult de doua ori: O(n) total.

Gasire subarray cu suma egala cu target (Python), verificat:

def subarray_with_sum(arr, target):
    left = 0
    current_sum = 0
    for right in range(len(arr)):
        current_sum += arr[right]
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        if current_sum == target:
            return (left, right)
    return None

arr = [1, 4, 2, 3, 6, 1, 2]
result = subarray_with_sum(arr, 9)
print("Array:", arr)
print("Target: 9")
if result:
    l, r = result
    print(f"Found at indices [{l}, {r}]: {arr[l:r+1]}")
    print(f"Sum: {sum(arr[l:r+1])}")

Output real (rulat cu python):

Array: [1, 4, 2, 3, 6, 1, 2]
Target: 9
Found at indices [1, 3]: [4, 2, 3]
Sum: 9

⚡ EXCLUSIV INTENSIV — Doi pointeri in C++

#include <iostream>
#include <vector>
using namespace std;

pair<int,int> subarrayWithSum(const vector<int>& arr, int target) {
    int left = 0, currentSum = 0;
    for (int right = 0; right < (int)arr.size(); right++) {
        currentSum += arr[right];
        while (currentSum > target && left <= right) {
            currentSum -= arr[left++];
        }
        if (currentSum == target) return {left, right};
    }
    return {-1, -1};
}

int main() {
    vector<int> arr = {1, 4, 2, 3, 6, 1, 2};
    auto [l, r] = subarrayWithSum(arr, 9);
    cout << "Array: [1, 4, 2, 3, 6, 1, 2]" << endl;
    cout << "Target: 9" << endl;
    if (l != -1) {
        cout << "Gasit la indicii [" << l << ", " << r << "]" << endl;
        cout << "Suma: 9" << endl;
    }
    return 0;
}

Output real (compilat g++ -std=c++17, apoi rulat):

Array: [1, 4, 2, 3, 6, 1, 2]
Target: 9
Gasit la indicii [1, 3]
Suma: 9

6

6. Alegerea structurii de date — cum decizi?

Structura de date potrivita depinde de operatiile dominante: daca ai nevoie de cautare frecventa, alege hash map (O(1)); daca ai nevoie de ordine, alege set/map (O(log n)); daca accesezi prin indice, alege vector (O(1)). Alegerea gresita poate schimba complexitatea cu un factor n.

Exemplu: gasirea elementului cel mai frecvent (C++), verificat:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 3};
    // O(1) amortizat per insertie/cautare
    unordered_map<int, int> freq;
    for (int x : v) freq[x]++;

    // Gasim elementul cu frecventa maxima
    auto it = max_element(freq.begin(), freq.end(),
        [](const auto& a, const auto& b){ return a.second < b.second; });
    cout << "Cel mai frecvent: " << it->first
         << " (" << it->second << " aparitii)" << endl;
    return 0;
}

Output real (compilat g++ -std=c++17, apoi rulat):

Cel mai frecvent: 3 (3 aparitii)

Structura	Acces index	Cautare valoare	Insertie	Iterare sortata
vector	O(1)	O(n)	O(1) amortizat*	Nu
unordered_map	N/A	O(1) amortizat	O(1) amortizat	Nu
map / set	N/A	O(log n)	O(log n)	Da

*Insertie la sfarsit; insertie la inceput/mijloc este O(n).

Tehnici de optimizare: alegerea structurii/algoritmului potrivit

Obiectivul lectiei

Dupa aceasta lectie vei putea:

Incearca singur!

1. De ce optimizam? — costul alegerii gresite

2. Memoizare — evitarea recalcularii

3. Precompute — sume prefix pentru interogari rapide

4. Fereastra glisanta — subarray-uri de lungime fixa

5. Doi pointeri — subarray cu suma data

6. Alegerea structurii de date — cum decizi?

Exercitii practice

Exercitiul 1 (Nivel minim) — Sume prefix

Exercitiul 2 (Nivel standard) — Fereastra glisanta

Exercitiul 3 (Nivel performanta) — Combinatie de tehnici EXCLUSIV INTENSIV

Ce ai invatat astazi

Modulul complet!