Slides TD Parcial2-11-20

Vista previa del material en texto

Notación Θ: cota ajustada asintótica
Θ(g(n)) = { f (n) | existen c1, c2 > 0 y n0 > 0 tal que
0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n) para todo n ≥ n0}
= O(g(n)) ∩ Ω(g(n))
14
Notación Θ: cota ajustada asintótica
Veamos que 53n + 5 está en Θ(n).
I Queremos ver que existen c1, c2 > 0 y n0 > 0 tal que
0 ≤ c1 · n ≤ 53n + 5 ≤ c2 · n para todo n ≥ n0.
I Ya mostramos que vale 53n + 5 ≤ c2 · n con c2 = 53 + 5 y n0 = 1.
I 0 ≤ c1 · n vale para c1 > 0 porque n0 > 0.
I Para que se cumpla la desigualdad del medio necesitamos:
c1 · n ≤
5
3
n + 5
c1 ≤ (
5
3
n + 5)/n
c1 ≤
5
3
+
5
n
I Tomando c1 = 53 la desigualdad vale para todo n ≥ n0.
15
Notación Θ: cota superior asintótica
Veamos que 53n + 5 está en Θ(n).
0 2 4 6 8 10
0
20
40
60
5
3n + 5
( 53 + 5) · n
5
3 · n
16
Peor caso, caso promedio, mejor caso
Sea A un algoritmo que toma una entrada de tamaño n, nos interesa
analizar su costo T (n).
I Peor caso: Dado n, ¿qué valores tiene que tomar la entrada para
que el algoritmo tenga el costo computacional más alto?
I Caso promedio: Dado n, ¿cuál es el costo computacional
promedio considerando la probabilidad de todos los posibles
valores de entrada de tamaño n?
I Mejor caso: Dado n, ¿qué valores tiene que tomar la entrada
para que el algoritmo tenga el costo computacional más bajo?
I La elección de entre estos casos potencialmente cambia el costo
T (n) obtenido.
I No confundir estos casos con los órdenes O,Ω,Θ. Son conceptos
independientes.
I En esta materia nos concentraremos únicamente en el peor caso.
17
Peor caso, caso promedio, mejor caso
¿Cuál es el tamaño de la entrada para este problema? ¿Cuál es el peor
caso y el mejor caso para este algoritmo?
1 bool buscar(int elem, const vector<int> & v){
2 int res = false;
3 int i = 0;
4 while(i < v.size() && res == false){
5 if (v[i] == elem){
6 res = true;
7 }
8 i = i + 1;
9 }
10 return res;
11 }
I Tamaño de la entrada: |v |
I Peor caso: elem no está en v .
I Mejor caso: elem es el primer elemento de v .
18
Cálculo de complejidad de algoritmos imperativos
1. Determinar cuál es la medida de tamaño de entrada para el
algoritmo dado.
2. Determinar qué valores de entrada constituyen el peor caso del
algoritmo.
3. Derivar del código del algoritmo la función de costo T que toma el
tamaño de entrada como parámetro y calcula el costo
computacional para el peor caso.
4. Proponer una función f que será el órden de complejidad y
demostrar que, según corresponda, T ∈ O(f ), o T ∈ Ω(f ), o
T ∈ Θ(f ).
19
Problema de ordenamiento
Dado un vector de números enteros ordenar sus elementos en forma
creciente.
59 7 388 41 2 280 50 123
↓
2 7 41 50 59 123 280 388
3
Algoritmos O(n2)
▶ Selection sort
▶ Buscar el mínimo de la parte que falta ordenar y colocarlo al �nal de
la parte que ya está ordenada.
59 7 388 41 2 280 50 123
2 7 388 41 59 280 50 123
2 7 41 388 59 280 50 123
2 7 41 388 59 280 50 123
. . .
▶ Insertion sort
▶ Tomar el próximo elemento de la parte que falta ordenar e insertarlo
de manera ordenada en la parte que ya está ordenada.
59 7 388 41 2 280 50 123
7 59 388 41 2 280 50 123
7 59 388 41 2 280 50 123
7 41 59 388 2 280 50 123
. . .
▶ Bubble sort
▶ De izquierda a derecha comparar pares de elementos vecinos e
intercambiarlos si corresponde. Repetir n veces.
4
Merge sort
Es un algoritmo recursivo para resolver el problema en Θ(n log n) en
peor caso.
59 7 388 41 2 280 50 123
▶ Dividir la secuencia en dos mitades.
59 7 388 41 2 280 50 123
▶ Ordenar cada mitad recursivamente.
7 41 59 388 2 50 123 280
▶ Combinar ambas mitades de manera ordenada.
2 7 41 50 59 123 280 388
5
Mergesort es Divide & Conquer
Divide & Conquer es una técnica de diseño de algoritmos que
estructura la solución de un problema de tamaño N así:
1. Caso base: Si el problema es su�cientemente pequeño, resolverlo
directamente; si no...
2. Divide: Partir el problema a resolver en b subproblemas de
tamaño N/a
3. Resolver los subproblemas (en general recursivamente)
4. Conquer: combinar los resultados de los subproblemas para
resolver el problema original
En Mergesort: Caso base si el arreglo es de tamaño 1 (está
ordenado); si no, realizamos divide y partimos el arreglo en dos
mitades iguales (a=2, b=2), luego ordenamos cada mitad por
separado, y �nalmente hacemos conquer al combinar los dos
subarreglos ordenados.
6