Slides TD Parcial2-1-10

Vista previa del material en texto

Repaso noción de complejidad algorítmica
Dado un vector de enteros no vacío y ordenado de forma creciente,
¿cuál algoritmo elegirían para encontrar el mínimo del vector?
1 int minimo(const vector<int> & v){
2 int res = v[0];
3 int i = 0;
4 while(i < v.size()){
5 if (v[i] < res){
6 res = v[i];
7 }
8 i = i + 1;
9 }
10 return res;
11 }
1 int minimo(const vector<int> & v){
2 return v[0];
3 }
El primero toma tiempo lineal y el segundo tiempo constante.
3
Repaso noción de complejidad algorítmica
Complejidad algorítmica es una herramienta para analizar algoritmos
según su consumo de recursos, en particular su tiempo de ejecución.
I La pregunta central es ¿cómo crece el tiempo de ejecución en
función del tamaño de la entrada?
I Las operaciones sobre tipos básicos toman tiempo constante.
I Ej: 2 + 7, 75.0/3.2, 5 > 0
I La lectura y escritura de variables de tipos básicos toman tiempo
constante.
I Ej: int i = 0, i = i + 1, char c = 'a'
I El costo de un ciclo es el costo de ejecutar el cuerpo multiplicado
por el costo de cada iteración.
I [Nuevo] El costo de las operaciones de tipos de la biblioteca
estándar está indicado en su documentación.
I Ej: las operaciones v[i] y v.size() toman tiempo constante
https://es.cppreference.com/w/cpp/container/vector/operator_at
https://es.cppreference.com/w/cpp/container/vector/size
4
https://es.cppreference.com/w/cpp/container/vector/operator_at
https://es.cppreference.com/w/cpp/container/vector/size
Repaso noción de complejidad algorítmica
I En TD1: este algoritmo tiene complejidad O(n), donde n = |v |.
I Pero, ¿qué significa exactamente la O?
1 int minimo(const vector<int> & v){
2 int res = v[0]; // 2 operaciones constantes
3 int i = 0; // 1 operacion constante
4 while(i < v.size()){ // n iteraciones
5 // 3 ops. const. (condición while)
6 if (v[i] < res){ // 4 operaciones constantes
7 res = v[i]; // 3 operaciones constantes
8 }
9 i = i + 1; // 2 operaciones constantes
10 }
11 return res; // 1 operacion constante
12 }
Costo temporal T (n) = 2 + 1 + n · (3 + 4 + 3 + 2) + 1
= 4 + 12n
6
Orden de complejidad O,Ω,Θ
El órden de complejidad indica en qué medida crece el tiempo de
ejecución de un algoritmo a medida que crece el tamaño de la
entrada. Formalmente es el conjunto de todas las funciones cuyo
ritmo de crecimiento es el mismo asintóticamente.
Por ejemplo, las siguientes
funciones...
I 5
3n + 5
I 2n
I 2
3n
3 + 8
I 7n2 + n
I 3n + 5
I n2 + 5
I 2n3 + 3
Nos gustaría agruparlas así:
I Órden lineal
I 2n, 3n + 5, 53n + 5
I Órden cuadrático
I n2 + 5, 7n2 + n
I Órden cúbico
I 2n3 + 3, 23n
3 + 8
7
Notación O: cota superior asintótica
O(g(n)) = { f (n) | existen c > 0 y n0 > 0 tal que
0 ≤ f (n) ≤ c · g(n) para todo n ≥ n0}
8
Notación O: cota superior asintótica
Veamos que 53n + 5 está en O(n).
I Queremos ver que existen c > 0 y n0 > 0 tal que 0 ≤ 53n + 5 ≤ c · n
para todo n ≥ n0.
I La desigualdad 0 ≤ 53n + 5 vale porque n0 > 0.
I Para que se cumpla la segunda desigualdad necesitamos:
5
3
n + 5 ≤ c · n
(
5
3
n + 5)/n ≤ c
5
3
+
5
n
≤ c
I Tomando n0 = 1 y c = 53 + 5, la desigualdad vale para todo n ≥ n0.
9
Notación O: cota superior asintótica
Veamos que 53n + 5 está en O(n).
0 2 4 6 8 10
0
20
40
60
5
3n + 5
( 53 + 5) · n
10
Notación Ω: cota inferior asintótica
Ω(g(n)) = { f (n) | existen c > 0 y n0 > 0 tal que
0 ≤ c · g(n) ≤ f (n) para todo n ≥ n0}
11
Notación Ω: cota inferior asintótica
Veamos que n2 + 7 está en Ω(10n).
I Queremos ver que existen c > 0 y n0 > 0 tal que
0 ≤ c · 10n ≤ n2 + 7 para todo n ≥ n0.
I La desigualdad 0 ≤ c · 10n vale para c > 0 porque n0 > 0.
I Para que se cumpla la segunda desigualdad necesitamos:
c · 10n ≤ n2 + 7
c ≤ (n2 + 7)/10n
c ≤ n
10
+
7
10n
I Con c ≤ n10 la desigualdad vale, ya que n10 ≤ n10 + 710n .
I Tomando n0 = 1 y c = 110 , la desigualdad vale para todo n ≥ n0.
12
Notación Ω: cota inferior asintótica
Veamos que n2 + 7 está en Ω(10n).
0 2 4 6 8 10
0
20
40
60
80
100
n2 + 7
1
10 · 10n
13