Subscribe to DeepL Pro to translate larger

Visit [Link]/pro for more infor

Complexitatea algoritmilor
Complexitatea algoritmică a problemelor de calcul

Dorel Lucanu

Facultatea de Informatică
Universitatea Alexandru Ioan Cuza, Iași,

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 1 /76

 România
dlucanu@[Link]

PA 2022/2023

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 2 /76

 Schiță

1 Recapitulare

2 Eficiența algoritmului: funcții de

cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul

5 Complexitatea sortării

6 Reducerea polinomială a
problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 3 /76

 Recap
itulare

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a
problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 4 /76

 Recapitulare

Limbajul algoritmic Alk

fact(n){
f=1;
p e n t r u ( i = 2 ; i <= n ;
++i ) f �= i ;
r e tu r n f ;
}

b=fact(a);

Dorim să o rulăm pentru a=21:

$ a l k i -a f a c t . a l k -i " a |-> 21 " -m
a |-> 21
b |-> 51090942171709440000

Opțiunea -m este pentru afișarea stării finale.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 5 /76

 Recap
itulare

Semantică: Execuție

Configurația inițială �S0 , σ0 ⟩ include algoritmul (codul Alk) ce urmează a

fi executat S0 și starea inițială σ0 .
Configurația finală �Sn , σn �, care există numai dacă execuția este
finită, nu are configurații succesoare (nu mai este nimic de executat).
Un algoritm este determinist dacă, pentru orice execuție și pentru orice
configurație a execuției respective, există cel mult o configurație
succesoare.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 6 /76

 Recapitulare

Problemă rezolvată de un algoritm

Un algoritm determinist A rezolvă o problemă P dacă:

conceptele din domeniul problemei sunt reprezentate prin structuri de
date;
pentru orice instanță (intrare) p din P, există o configurație inițială
⟨A, σp �; astfel încât σp include structuri de date care descriu p;
execuția pornind de la configurația inițială ⟨A, σp � se termină
într-o configurație finală ⟨-, σ′ �, scrie ⟨A, σ⟩ ⇒∗ �., σ′ �; și
σ′ include structuri de date care descriu rezultatul P(p).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 7 /76

 Recapitulare

Problemă rezolvabilă/computabilă/decidabilă

O problemă P este rezolvabilă (calculabilă) dacă există un algoritm A

care rezolvă P.
O problemă P este nesoluționabilă (necomputabilă) dacă NU există un
algoritm A care să rezolve P.
O problemă de decizie P are răspunsul (output) de forma "DA" sau
"NU" (în mod echivalent, "adevărat" sau "fals").
O problemă de decizie este în general prezentată de o pereche (instanță,

întrebare). O problemă decidabilă este o problemă de decizie care

poate fi rezolvată.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 8 /76

O problemă nehotărâbilă este o problemă de decizie care nu poate fi
rezolvată.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 9 /76

 Eficiența algoritmului: funcții de
cost

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 10 /

 Eficiența algoritmului: funcții de cost

Povestea unui proiect privind usturoiul1 1/2

1RFagin. Aplicarea teoriei (inclusiv a logicii cu valori reale) în practică.

Workshop FMTMVLCI.
[Link]
[Link]
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 9/
 Eficiența algoritmului: funcții de cost

Povestea unui proiect privind usturoiul2 2/2

2RFagin. Aplicarea teoriei (inclusiv a logicii cu valori reale) în practică.

Workshop FMTMVLCI.
[Link]
[Link]
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 10 /
 Eficiența algoritmului: funcții de cost Valoare
Dimensiune

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 11 /76

 Eficiența algoritmului: funcții de cost Valoare Dimensiune

Cu privire la tipurile de date

Un tip de date este format din valori (constante) și operații.

Fiecare valoare este reprezentată cu ajutorul unui spațiu

de memorie.
Pentru valorile fiecărui tip de date, trebuie menționată dimensiunea de
reprezentare.
Există (cel puțin) trei moduri de a defini mărimea valorilor:
uniform: |v |unif
logaritmică: |v |log
liniar: |v |lin

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 12 /76

 Eficiența algoritmului: funcții de cost Valoare Dimensiune

Exemple de mărime a valorilor

numere întregi:
Int = {. . . , -2, -1, 0, 1, 2, . . .}
dimensiune uniformă: |n|unif = 1
dimensiune logaritmică: |n|log = log2 abs(n)
dimensiune liniară: |n|lin = abs(n)
array-uri:
valoare: a = [a0 , a1 , . . . . , a ]n−1
dimensiune: |a|d = |a | |0d + |a |1d + - - - - + |a |n−1d , d ∈ {unif, log,
lin}
array-urile bidimensionale sunt array-uri de array-uri unidimensionale,
array-urile tridimensionale sunt array-uri de array-uri
bidimensionale, etc.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 13 /76

 Eficiența algoritmului: funcții de cost Costul în timp al evaluării
operațiunii

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 14 /76

 Eficiența algoritmului: funcții de cost Costul în timp al evaluării operațiunii

Tipul de date (continuare)

Tipul de date = valori + operații

Fiecare operație op are un cost de timp time(op).

Pentru fiecare operațiune de orice tip de date trebuie menționat timpul de

cost.

Există trei moduri de măsurare a timpului (moștenite de la dimensiunea

valorii):
uniform: timeunif (op) - utilizează dimensiunea uniformă a valorilor
logaritmic: timelog (op) - utilizează dimensiunea logaritmică a valorilor
linear: timelin (op) - utilizează dimensiunea liniară a valorilor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 15 /76

 Eficiența algoritmului: funcții de cost Costul în timp al evaluării operațiunii

Exemple de costuri temporale ale operațiunilor

adunarea numerelor întregi a +Int b
uniformă: O(1)
logaritmic: O(max(log a, log b))
liniar: O(a + b)
căutare de matrice
// σk : . . . a '→ A . . . . i '→ i0 . . . . .
x=a[i];
// σk+1 : . . . a '→ A . . . . i '→ i0 . . . . x '→ [Link](i0 ) . . . .
costul timpului
uniformă: O(1)
logaritmic: O(i0 + |A[i0 ]|log )
linear: O(|A[i0 ]| )lin
Observ
ație
Costul de timp al operațiilor asupra listelor, seturilor, hărților depinde de implementare (array-
uri, liste legate, . . . ) (a se vedea cursul de structură a datelor). De fapt, Alk este abstract în
ceea ce privește implementarea operațiilor din definiția sa. Prin urmare, analiza timpului poate fi
efectuată numai în funcție de o implementare. De exemplu, există mulți algoritmi pentru
înmulțirea a doi numere întregi. Atunci când este nevoie de timpul logaritmic pentru această
operație, trebuie să-l luăm pe cel corespunzător implementării presupuse. Evident, această
abordare este cea mai precisă, dar dificil de manevrat în practică. Prin urmare, restricționăm
acest tip de ipoteze doar la liste, hărți, seturi etc.
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme AP 2022/2023 16 / 68
calcul onale
 Eficiența algoritmului: funcții de cost Costul de timp al evaluării unei expresii și al unei etape de calcul

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 17 /76

 Eficiența algoritmului: funcții de cost Costul de timp al evaluării unei expresii și al unei etape de calcul

Costul în timp al evaluării unei expresii

Evaluarea expresiilor: [E ]]](σ) - valoarea lui E în starea σ
Exemplu: σ = a '→ 3 b '→ 6
[a + b ∗ 2]](σ) = [a]](σ) +Int [b ∗ 2]](σ) = 3 +Int [b]](σ) ∗Int [2]](σ)=
3 +Int 6 ∗Int 2 = 3 +Int 12 = 15
unde +Int reprezintă algoritmul pentru adunarea numerelor întregi și ∗Int reprezintă
algoritmul pentru înmulțirea numerelor întregi.
Costul de timp al evaluării unei expresii este suma costurilor de timp ale
operațiilor incluse în expresie.
Evident, poate fi uniformă, logaritmică sau liniară. Exemplu:
timpuld ([[a + b ∗ 2]](σ)) =
timpd ([[a]](σ)) + timpd ([[b]](σ)) + timpd (6 ∗Int 2) + timpd (3 +Int 122),
d ∈ {unif, log, lin}.
σ = a '→ 3 b '→ 6
timplog ([[a]](σ)) = log 3, timplog ([[b]](σ)) = log 6
timpunif ([[a]](σ)) = 1, timpunif ([[b]](σ)) = 1
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 18 /76
timplin ([[a]](σ)) = 3, timplin ([[b]](σ)) = 6

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 19 /76

 Eficiența algoritmului: funcții de cost Costul de timp al evaluării unei expresii și al unei etape de calcul

Costul în timp al unei etape de execuție a unei instrucțiuni

O etapă de execuție este o pereche ⟨S, σ⟩ ⇒ �S′ , σ′ �, ceea ce înseamnă că
după prima etapă din
S se execută în starea σ, obținem S′ și σ′ .
Costul de timp al unei etape de execuție a unei instrucțiuni depinde de starea
σ și de instrucțiunea executată.
Exemple:
�V = E ; S, σ⟩ ⇒ ⟨S, σ′ ⟩ , unde σ′ = σ[V '→ [E ]]](σ)
timpul de execuție este egal cu timpul de evaluare a lui E în starea σ3 ;
⟨if (E ) S1 else S2 S, σ� ⇒ �Si S, σ⟩
timpul de execuție este egal cu timpul de evaluare a lui E în starea σ;
în timp ce instrucțiunea (E ) S S S′ poate fi înlocuită cu una echivalentă
if (E ) {S while (E ) S } S′ ;
...
Din nou, poate fi uniformă, logaritmică sau liniară.
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 20 /76
3O analiză mai atentă ar putea lua în considerare și operatorul de atribuire.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 21 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 22 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Costul în timp al unui calcul (execuție)

Un calcul (o execuție) este o secvență de etape de execuție:

τ = �S1 , σ1 ⟩ ⇒ �S2 , σ2 ⟩ ⇒ �S3 , σ3 ⟩ ⇒ . . . .

Costul în timp al unui calcul:

timed (τ ) = Σi timed (�Si , σi ⟩ ⇒ �Si+1 , σi+1

�), unde d ∈ {unif , log, lin}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 23 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Dimensiunea (spațiu) costul unui calcul (execuție)

Dimensiunea (spațiul) unei stări σ este suma dimensiunilor valorilor stocate

în σ. Dimensiunea (spațiul) unui calcul:

dimensiuned (τ ) = maxi dimensiuned (σi ),

unde τ = �S1 , σ1 ⟩ ⇒ �S2 , σ2 ⟩ ⇒ �S3 , σ3 ⟩ ⇒ . . . și
d ∈ {unif , log, lin}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 24 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Costuri de calcul: exemplu

�if (x > 3) x = x + y; else x = 0; y = 4; , x '→ 7 y '→ 12⟩ ⇒

�x = x + y; y = 4; , x '→ 7 y '→ 12⟩ ⇒
⟨y = 4; , x '→ 19 y '→ 12⟩ ⇒
⟨-, x '→ 19 y '→ 4⟩
Evaluările expresiei utilizate:
[x > 3]]](x '→ 7 y '→ 12) = 7 > 3 = true
[x + y]](x '→ 7 y '→ 12) = 7 + 12 = 19
[4]](x '→ 19 y '→ 12) = 4
Costul de calcul:
cost uniform: 3 (= numărul de pași) cost
logaritmic: log 7 + log 12 + log 19 + log 4
cost liniar: 7 + 12 + 19 + 4

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 25 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Calcularea funcțiilor de cost cu interpretorul Alk 1/3

Se consideră algoritmul care calculează suma primelor n numere întregi:

sumă ( n )
// r e q u i r e s n >= 0
{
s=0;
i=0;
dacă ( i < n ) {
i ++;
s=s+i;
}
returnes;
}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 26 /76

 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Calcularea funcțiilor de cost cu interpretorul Alk 2/3

Adăugăm instrucțiuni de calcul al funcțiilor de cost al timpului (rețineți că
log(x ) returnează logaritmul în baza e):
#i n c l u d e " ops-time . a l k "

timeSum ( n , time Tip )

// r e q u i r e s n >= 0
{
t ime = 0 ;
s=0;
t ime += timeOpUn ("=" , time Type , s ) ;
i=0;
t ime += timeOpUn ("=" , time Type , i ) ;
dacă ( i < n ) {
t ime += time Op Bin ("<" , time Type , i , n ) ;
i ++;
t ime += timeOpUn ("++" , time Type , i ) ;
s=s+i;
t ime += time Op Bin ("+" , time Type , i , s ) ;
}
r e t u r n t ime ;
}
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 27 /76
 Eficiența algoritmului: funcții de cost Costul în timp/spațiu al unui calcul

Calcularea funcțiilor de cost cu interpretorul Alk 3/3

Execută-l:
t i m e u n i f = timeSum ( 1 0 0 0 , " u n i f "
) ; t i m e l o g = timeSum ( 1 0 0 0 , " l o g "
);
t i m e l i n = timeSum ( 1 0 0 0 , " l i n " ) ;

Configurația finală:
t i m e u n i f |-> 302 O(n)
t i m e l o g |-> 2282 O(log n!), de
ce? t i m e l i n |-> 191800 O(n4 ), de
ce?

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 28 /76

 Complexitatea în cel mai
rău caz

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 29 /76

 Complexitatea în cel mai rău caz

Dimensiunea unei instanțe de problemă

Dimensiunea unei stări σ este

Σ
dimensiune x'→v dimensiuned (v )
d (σ) = �σ

Dimensiunea unei configurații este

dimensiuned (⟨A, σ�) =
dimensiuned (σ) unde d ∈ {log, unif , lin}.
Fie P o problemă, p ∈ P și A un algoritm determinist care rezolvă P.
Dimensiunea lui p este dimensiunea configurației sale inițiale:
sized (p) = sized (⟨A, σp �) (= size(σp ))
unde d ∈ {log, unif , lin}.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 30 /76

 Complexitatea în cel mai rău caz

Complexitatea de timp în cel mai rău caz

Fie P o problemă și A un algoritm determinist care rezolvă P și fixați

d ∈ {log, unif , lin}.
Grupați instanțele p din P în clase de echivalență: p și p′ se află în aceeași
clasă de echivalență dacă size(p) = size(p ).′
Un număr natural n poate fi considerat ca fiind clasa de echivalență a
instanțelor p de dimensiune n (dimensiuned (p) = n).
Complexitatea timpului în cel mai rău caz:
TA,d (n) = sup{timpd (A, p) | p ∈ P, dimensiuned (p) = n}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 31 /76

 Complexitatea în cel mai rău caz

Complexitatea spațială

Fie E = ⟨A0 , σ0 ⟩ ⇒ - - - - - ⇒ �An , σn ⟩ o execuție și să se fixeze

d ∈ {log, unif , lin}
Spațiul utilizat de această execuție este:

distanțate (E )= i dimensiuned (�Ai , σi �)}

maxn =0

Spațiul necesar algoritmului A pentru rezolvarea instanței p ∈ P este

spaced (A, p) = spaced (Ep
) unde Ep este execuția corespunzătoare lui p.
Complexitatea spațială în cel mai rău caz:
SA,d (n) = sup{spaced (A, p) | sized (p) = n}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 32 /76

 Complexitatea în cel mai rău caz

Calcularea complexității temporale în cel mai rău caz:

Exemplul
@input
1/2
D un digraf, un vertex i0
@output S = setul de vârfuri la care se poate ajunge de la i0
D = {D.V , D.a}
D.a = harta listelor de adiacență
p = emptyMap ;
pentru fiecare din D. V p
[ i ] = D. a [ i ] ;

SB = <i 0 >;
S={i0};

în cazul în care ( SB . s i z e () > 0 )

{
i = SB . to p F ro n t ( ) ;
dacă ( p [ i ] . s i z e () == 0 ) {
SB . pop Front ( ) ;
}
else{
j = p [ i ] . to p F ro n t ( ) ;
p [ i ] . pop Front ( ) ;
i f ( ! ( j i n S )) {
// v i s i t j
S=SU{j};
SB . p u s h F ro n t ( j ) ;
}
}
}
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 33 /76
 Complexitatea în cel mai rău caz

Calcularea complexității temporale în cel mai rău caz:

Exemplul
tipul de2/2
cost: uniform
dimensiunea unei instanțe: n = D.V .size()
ipoteze: time([Link]()) = O(1), time([Link]()) = O(1),
time([Link](j)) = O(1), time(S ∪ {j}) = O(1) 4
operațiile analizate: toate cele care implică vârfuri
în cel mai rău caz: D.a[i ].size() = n - 1 pentru fiecare i (un digraf
complet) foreach: O(n), presupunând că timpul pentru p[i ] = D.a[i
];
Σ este O(1) while: numărul de iterații pentru cel mai rău caz este
D.a[i ].size() = n - (n -
i
timpul
1) pentru while-body este O(1), deoarece toate operațiile din interior au
aceeași valoare.
timp de execuție O(1)
timpul de execuție pentru cel mai rău caz:
TA (n) = O(1) + O(n) + n - (n - 1) - O(1) = O(n )2
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 34 /76
 4Alk
este abstract în ceea ce privește implementarea operațiilor din definiția sa. Prin urmare, sunt necesare astfel de
ipoteze și trebuie să fie o implementare a Alk cu timpii de execuție presupuși. Analiza timpilor se poate face numai în raport cu o
implementare.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 35 /76

 Complexitatea (algoritmică) a problemelor de calcul

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 36 /76

 Complexitatea (algoritmică) a problemelor de calcul

De ce?

O problemă poate fi rezolvată prin mai mulți algoritmi.

De fapt, dacă există un algoritm care să rezolve această problemă,

atunci există o infinitate. (De ce?)

Definiția din eficiența algoritmilor poate fi extinsă la probleme.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 37 /76

 Complexitatea (algoritmică) a problemelor de calcul

Reamintim povestea proiectului

Garlic Project5

Cum?
5RFagin. Aplicarea teoriei (inclusiv a logicii cu valori reale) în practică. Workshop
FMTMVLCI.
[Link]
[Link]
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 38 /76
 Complexitatea (algoritmică) a problemelor de calcul

Când știm UN algoritm care rezolvă problema

Luați în considerare:
o problemă P
n = size(x ), x ∈ P o instanță a lui P
un algoritm A care rezolvă P cu timpul de execuție în cel mai rău caz
O(f (n)) Ce putem spune despre complexitatea în timp a lui P?

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 39 /76

 Complexitatea (algoritmică) a problemelor de calcul

Complexitatea O(f (n)) a unei probleme

Aceasta oferă o limită superioară pentru efortul de calcul necesar pentru a

rezolva o problemă.
Definiție
O problemă P are complexitatea în timp în cel mai rău caz O(f (n)) dacă
există un algoritm A care rezolvă P și TA (n) = O(f (n)).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 40 /76

 Complexitatea (algoritmică) a problemelor de calcul

Când vrem să știm ceva despre TOȚI algoritmii

Luați în considerare:
o problemă P
n = size(x ), x ∈ P o instanță a lui P
Ce fel de informații putem furniza despre toți algoritmii care rezolvă P

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 41 /76

 Complexitatea (algoritmică) a problemelor de calcul

Complexitatea Ω(f (n)) a unei probleme

Acesta furnizează o limită inferioară pentru efortul de calcul necesar pentru

a rezolva o problemă.
Definiție
O problemă P are complexitatea în timp în cel mai rău caz Ω(f (n)) dacă
orice algoritm
A care rezolvă P are TA (n) = Ω(f (n)).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 42 /76

 Complexitatea (algoritmică) a problemelor de calcul

Un algoritm optim pentru o problemă

Luați în considerare:
o problemă P
n = size(x ), x ∈ P o instanță a lui P
Când un algoritm este optim pentru P?
Definiție
A este un algoritm optim (în ceea ce privește complexitatea în timp în cel
mai rău caz) pentru P dacă
A rezolvă P și
P are o complexitate de timp în cel mai rău caz Ω(TA (n)).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 43 /76

 Complexitatea sortării

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 44 /76

 Complexitatea sortării

Problema de
sortare

Să luăm în considerare cazul particular al sortării array-urilor:

TRIMITE
@domeniu Presupunem că (U , ≤) este un ansamblu (univers)
total ordonat. @input n și matricea a = [v0 , . . . . , vn−1 ]
cu vi ∈ U. @output Un array a′ = [w0 , . . . . , wn−1 ] cu
proprietatea:
w0 ≤ - - - - - ≤ wn−1 și w = (w0 , . . . , wn−1 ) este o permutare
a
v = (v0 , . . . . , v ).n−1
Notație:
SORTED(w ): secvența w este sortată (ordonată în mod nedecrescător)
Perm(v, w ): w este o permutare a lui v

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 45 /76

 Complexitatea sortării

BubbleSort: algoritmul

bubbleSort(out a) {
last = [Link]()-1;
askIth(out a, i)
while (last > 0)
{
{
if (a[i] > a[i+1])
oldLast =
{ temp = a[i];
last; i = 0;
a[i] = a[i+1];
while (i < oldLast)
a[i+1] = temp;
{
return i;
last = askIth(a, i);
}
i = i + 1;
returnează 0;
}
}
}
}

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 46 /76

 Complexitatea sortării

Analiza algoritmului BubbleSort

Timp de execuție
mărimea instanței: n (= [Link]())
operații măsurate: comparații care implică elementele tabloului
cazul cel mai defavorabil: când elementele tabloului sunt în ordine
descrescătoare, numărul de comparații pentru acest caz este
(n - 1)n
(n - 1) + (n - 2) + - - - - + 1 = = O(n )2
2

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 47 /76

 Complexitatea sortării

InsertSort: algoritmul

insertSort(out a, n) {
for (j = 1; j < n; j = j+1) {
i = j - 1;
temp = a[j];
while ((i >= 0) && (temp < a[i]))) {
a[i+1] = a[i];
i = i - 1;
}
if (i != j-1) a[i+1] = temp;
}
}

Notă. Este necesară evaluarea în scurtcircuit pentru expresiile booleene.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 48 /76

 Complexitatea sortării

Analiza algoritmului InsertSort

Timp de execuție
mărimea instanței: n (= [Link]())
operații măsurate: comparații care implică elementele tabloului cel
mai rău caz: când secvența de intrare este descrescătoare
- căutarea lui i în a[0 ... j - 1] necesită j - 1 comparații
numărul de comparații pentru acest caz
(n - 1)n
este 1 + 2 + - - - - + (n - 1) = =
O(n )2
2

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 49 /76

 Complexitatea sortării

HeapSort: algoritmul
insertInHeap(out a, n, ℓ) {
isHeap = false; j = ℓ;
while (2*j+1 <= n-1 && ! isHeap)
{ k = 2*j +1;
dacă ((k < n-1) && (a[k] < a[k+1])) k = k+1;
if (a[j] < a[k]) swap(a, j, k); else isHeap = true;
j = k;
}
}
Notă. Este necesară evaluarea în scurtcircuit pentru expresiile booleene.
heapSort(out a, n) {
for (l = (n-1)/2; l >= 0; l = l-1)
insertInHeap(a, n, l);
r = n-1;
while (r >= 1) {
swap(a, 0, r);
insertInHeap(a, r, 0);
r = r - 1;
}
}
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 50 /76
 Complexitatea sortării

HeapSort: analiza

Timp de execuție
mărimea instanței: n (= [Link]())
operații măsurate: comparații care implică elementele tabloului cel
mai rău caz: greu de spus
– complexitatea timpului pentru insertInHeap: O(log k), unde k este
heap-ul
dimensiune
– construcția grămezii inițiale necesită
O(logn−12 ) + - - - - + O(log n) = O(n log n) (de fapt, este Θ(n), a
se vedea Cormen et al., 6.3)
– complexitatea timpului pentru o perioadă de timp:
O(log (n - 1)) + O(log(n - 2)) + - - - - + O(log 1) = O(n log n)
numărul total de comparații O(n log n)
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 51 /76
 Complexitatea sortării

Alți algoritmi de sortare

Exerciții pentru seminar.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 52 /76

 Complexitatea sortării

Două întrebări referitoare la algoritmii de sortare

Algoritmii de sortare studiați până acum se bazează pe două operații

primitive: compararea și schimbarea a două elemente de tablou. Deoarece
permutarea este precedată de o comparație, putem presupune că operațiile
primitive esențiale sunt compararea a două elemente de matrice.

Următoarele două întrebări referitoare la complexitatea computațională a

sortării sunt destul de naturale:
Care este numărul minim de comparații în cel mai rău caz?
Ce algoritmi de sortare necesită numărul minim de comparații?
Pentru a răspunde la aceste întrebări, trebuie să definim în mod formal
modelul de calcul al algoritmilor bazați pe comparații (un tip special de arbori de
decizie).
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 53 /76
 Complexitatea sortării

Arbori de decizie pentru sortare: intuitiv

Ipoteză: ai ̸= aj dacă i ̸= j.
Notație: i ? j ≡ se compară a[i ] și a[j].
Un arbore de decizie pentru sortare include comparațiile efectuate de
algoritm:
un mod intern este etichetat cu i ? j, i , j ∈ {0, 1, . . . . , n -
1}; subarborele stâng al lui i ? j include comparațiile
pentru uni < aj ; subarborele drept al lui i ? j include
comparațiile pentru uni > aj ; nodurile externe (de
frontieră) sunt etichetate cu permutări

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 54 /76

 Complexitatea sortării

Algoritmii reprezentați ca arbori de decizie

Definiție
Un arbore de decizie pentru n elemente este un arbore binar
astfel încât: noduri interne: i ? j, i , j ∈ {0, 1, . . . . , n -
1};
noduri externe (de frontieră): permutări ale setului {0, 1, . . . . , n - 1}.
Definiție

Un calcul al unui arbore de decizie t pentru intrarea a = (a0 , . . .

. , an−1 ): o cale de la rădăcină la frontieră cu proprietatea:
dacă ai < aj : copilul stâng al lui i ? j este nodul
curent; în caz contrar, copilul drept devine nodul
curent calculul (ar trebui) să se încheie la frontieră

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 55 /76

 Complexitatea sortării

Arbori de decizie pentru sortare

Definiție
Un arbore de decizie t rezolvă problema de
sortare dacă pentru orice intrare de intrare
a = (a0 , . . . . , a ),n−1
calculul lui t pentru a se termină în π s.t. aπ(0) < - - - - < aπ(n-1).
Un arbore de decizie pentru sortare este un arbore de decizie
care rezolvă problema de sortare.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 56 /76

 Complexitatea sortării

Un arbore de decizie care reprezintă InsertSort

0?1

< >

1?2 0?2

< > < >

0?2 1,0,2 1?2

0,1,2
< > < >

0,2,1 2,0,1 1,2,0 2,1,0

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 57 /76

 Complexitatea sortării

Complexitatea în timp a sortării

Notații:
ADS (n) = setul de arbori de decizie pentru sortarea secvențelor de lungime
n.
Fr (t) = frontiera arborelui de decizie t
length(π, t) = lungimea în t a drumului de la rădăcină la π ∈ Fr (t).
Complexitatea în timp pentru cel mai rău caz:

T (n) = min max lungime(π, t)

t�ADS (n) π�Fr
(t)

Teorema

Problema de sortare are o complexitate de timp în cel mai rău caz Ω(n log
n) în modelul de calcul al arborilor de decizie pentru sortare.
Corolarul
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 58 /76
HeapSort este optim în modelul de calcul al arborilor de decizie pentru sortare.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 59 /76

 Reducerea polinomială a
problemelor

Plan

1 Recapitulare
2 Eficiența algoritmului: funcții de
cost Valoare Dimensiune
Evaluarea costului în timp al operațiunii
Costul în timp al evaluării unei expresii și al unei etape de calcul Costul
în timp/spațiu al unui calcul

3 Complexitatea în cel mai rău caz

4 Complexitatea (algoritmică) a problemelor de calcul
5 Complexitatea sortării
6 Reducerea polinomială a problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 60 /76

 Reducerea polinomială a
problemelor

Motivație

Mentalitate: "Dacă știu să rezolv o problemă Q, atunci pot folosi

acest algoritm pentru a rezolva P?".
Intuiție: O problemă P se reduce la Q dacă algoritmii pentru Q pot ajuta
la rezolvarea lui P.
Aplicație:
proiectarea algoritmului
dovada limitelor: dacă P este dificil, atunci și Q este dificil
clasificarea problemelor

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 61 /76

 Reducerea polinomială a problemelor

Reducerea Turing/Cook

O problemă P se reduce polinomial la (o problemă rezolvabilă) Q, se scrie

P ∝ Q, dacă putem concepe un algoritm pentru P
1
după cum urmează: fie p o instanță a lui P;
2
preprocesează în timp polinomial intrarea p pentru a obține o instanță
(sau instanțe) a lui Q;
3
apelați un algoritm pentru Q, posibil de mai multe ori (dar de timp
polinomial);
4
postprocesează ieș irile date de Q în timp polinomial pentru a
obține răspunsul P(p).
Dacă timpul de procesare (pre+post) necesită timp O(g (n)), atunci scriem
P �g (n) Q.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 62 /76

 Reducerea polinomială a problemelor

Exemplu: MAX ∝ SORT

FieSă fie MAX următoarea problemă:

@input Un set S total ordonat.
@output Cel mai mare element
din S . Următorul algoritm rezolvă
MAX:
1 reprezintă S cu un tablou s (preprocesare);
2 apelează un algoritm de sortare pentru s;
3 returnează ultimul element din s
(postprocesare); Așadar, avem MAX ∝ SORT!?
� nu înseamnă în mod necesar "reducerea unei probleme complexe la o
problemă complexă la o
mai ușor"!!!

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 63 /76

∝ este mai degrabă o "transformare"... .

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 64 /76

 Reducerea polinomială a problemelor

Variante pentru problema sumei de subseturi

SSD1
@input Un set S de numere întregi, M un număr întreg pozitiv.
Σ mai mare număr întreg M s.t. M ≤ M și ∃ S ⊆ S cu
@output Cel ∗ ∗ ′

x �S ′ x = M .∗

SSD2
@instanță Un set S de numere întregi, M, K două numereîntregi pozitive cu K
≤ M.
@întrebare Există M◦ s.t. K ≤ M◦ ≤ M și un ◦
x �S′ x = M pentru
′
anumit set S ⊆ S ? a
SSD3
@instance Un set S de numere întregi, M un număr în tr e g pozitiv.
@întrebare Există un subset S′ ⊆ S cu x �S′ x = M?

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 65 /76

 Reducerea polinomială a problemelor

Exemplu: SSD1 ∝ SSD2

SSD1
@input Un set S de numere întregi, M un număr întreg pozitiv.
Σ mai mare număr întreg M s.t. M ≤ M și ∃ S ⊆ S cu
@output Cel ∗ ∗ ′

x �S ′ x = M∗ .

SSD2
@instance Un set S de numere întregi, M, K două numere întregi pozitive cu K
≤ M.
Σ
@întrebare Există M◦ s.t. K ≤ M◦ ≤ M și x ◦
′ x = M pentru a
�S
un anumit set S′ ⊆ S ?
1 fără preprocesare;
2 găsiți M∗ în (0, M] apelând un algoritm care rezolvă SSD2 într-o
manieră de căutare binară.
Acesta este un exemplu în care o problemă de optimizare este redusă la o
problemă de decizie.
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 66 /76
 Reducerea polinomială a problemelor

Exemplu: SSD2 ∝ SSD1

SSD1
@input Un set S de numere întregi, M un număr întreg pozitiv.
Σ mai mare număr întreg M s.t. M ≤ M și ∃ S ⊆ S cu
@output Cel ∗ ∗ ′

∗
x �S ′ x = M .

SSD2
@instance Un set S de numere întregi, M, K două numere întregi pozitive cu K
≤ M.
Σ
@întrebare Există M◦ s.t. K ≤ M◦ ≤ M și x ◦
′ x = M pentru a
′ �S
un anumit set S ⊆ S ?
1 fără preprocesare;
2 se calculează M∗ ≤ M apelând un algoritm care
3 rezolvă SSD1; dacă M∗ ≥ K, atunci se returnează
"YES", altfel se returnează "NO";
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 67 /76
 Reducerea polinomială a problemelor

Exemplu: SSD3 ∝ SSD1

SSD1
@input Un set S de numere întregi, M un număr întreg pozitiv.
Σ mai mare număr întreg M s.t. M ≤ M și ∃ S ⊆ S cu
@output Cel ∗ ∗ ′

∗
x �S ′ x = M .

SSD3
@instance Un set S de numere întregi, M un
număr întreg pozitiv.
Σ ′ x = M?
@întrebare Există un subset S′ ⊆ S cu
x
�S
1 fără preprocesare;
2 se calculează M∗ ≤ M apelând un algoritm care
3 rezolvă SSD1; dacă M∗ = M se returnează "YES",
altfel se returnează "NO".

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 68 /76

 Reducerea polinomială a problemelor

Reducerea Karp

Fie P și Q probleme de decizie.

Problema P se reduce polinomial la (rezolvabila) Q, se scrie P ∝ Q,
dacă putem proiecta un algoritm care să rezolve P după cum urmează:
1
fie p o instanță a lui P;
2
preprocesează intrarea p în timp polinomial pentru a obține o
3
instanță q a lui Q; apelează (o singură dată) un algoritm care
rezolvă Q;
4
răspunsul pentru Q pentru q este același cu răspunsul pentru P
pentru p (fără postprocesare).
Dacă timpul de preprocesare este O(g (n)), atunci scriem P �g (n) Q.
Reducerea Karp este un caz particular al reducerii Turing/Cook.
D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 69 /76
 Reducerea polinomială a problemelor

Exemplu: SSD3 ∝ SSD2

SSD2
@instance Un set S de numere întregi, M, K două numere întregi pozitive cu K
≤ M.
Σ
@întrebare Există M◦ s.t. K ≤ M◦ ≤ M și x ◦
′ x = M pentru a
′ �S
un anumit set S ⊆ S ?
SSD3
@instance Un set S de numere întregi, M un
număr întreg pozitiv.
Σ ′ x = M?
@întrebare Există un subset S′ ⊆ S cu
x
�S
1 fără preprocesare;
2
se numește un algoritm care rezolvă SSD2 pentru instanța S, M, M.

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 70 /76

 Reducerea polinomială a problemelor

Exemplu: 3-SUMA ∝ 3-COLINIAR

3-SUM
@instance Un set S de n numere întregi.
@întrebare Există 3 numere în S s.t. suma lor este 0?
3-COLLINEAR
@instance Un set S de n puncte în plan.
@întrebare Există trei puncte în S care sunt coliniare? 3-
SUM ∝ 3-SUNT COLINIARE:
1
sconsiderăm o intrare S = {a0 ,3 a1 , . . . . 3, an−1 } din 3-SUM;3
2 se calculează t(S ) = {(a0 , a ), (a1 , a ), . . . . , (an−1 , a )}
0 1 n-1
3 returnează rezultatul dat de un algoritm care rezolvă 3-COLLINEAR
pentru
t(S ).

Lema
Dacă a, b, c sunt distincte, atunci a + b + c = 0 dacă (a, a3 ), (b, b3 ) și
(c, cD.3Lucanu
) sunt coliniare. Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023
(FII - UAIC) 71 /76
 Reducerea polinomială a problemelor

Reducere: proprietăți

Teorema
a) Dacă P are complexitatea în timp Ω(f (n)) și P ∝g (n) Q (versiunea
Karp), atunci se obține
Q are o complexitate în timp Ω(f (n) - g (n)).

b) Dacă Q are complexitatea în timp O(f (n)) și P �g (n) Q

(versiunea Karp), atunci P are complexitatea în timp O(f (n) + g
(n)).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 72 /76

 Reducerea polinomială a
problemelor

Un studiu de
caz

Următoarea este cunoscută sub numele de problema coifului convex:

CH
@input Un set de puncte P în plan.
@output Cel mai mic poligon convex care conține toate punctele din P.

Deoarece SORT ∝n CH, rezultă că CH are o complexitate în timp Ω(n log

n).

D. Lucanu (FII - UAIC) Complexitatea algoritmilor și a calculelor de Probleme PA 2022/2023 73 /76