Slides TD Parcial2-21-30

Vista previa del material en texto

Merge sort
vector<int> MergeSort(vector<int> V )
1. Si |V | ≤ 1:
Devolver V
2. med = |V |/2
3. izq = MergeSort(V [0 . . .med − 1])
4. der = MergeSort(V [med . . . |V | − 1])
5. Devolver Merge(izq, der)
Donde Merge(V 1,V 2) es una función que toma dos vectores ordenados
y devuelve la union ordenada de ambos.
7
Merge sort en C++
1 vector<int> mergesort(const vector<int> & v, int d, int h){
2 // Ordena los elementos desde d hasta h (sin incluir)
3
4 // Si hay 0 o 1 elementos, ya están ordenados
5 if(h - d == 0)
6 return {};
7 if(h - d == 1)
8 return {v[d]};
9
10 // Divide y ordena cada mitad
11 int med = (d+h)/2;
12 vector<int> izq = mergesort(v, d, med);
13 vector<int> der = mergesort(v, med, h);
14
15 // Devuelve la unión ordenada de ambas mitades
16 return merge(izq, der);
17 }
8
Merge sort � función merge
1 vector<int> merge(const vector<int> & v1, const vector<int> & v2){
2 vector<int> res; int i = 0; int j = 0;
3
4 while(i < v1.size() && j < v2.size()){
5 if(v1[i] < v2[j]){
6 res.push_back(v1[i]);
7 i++;
8 } else {
9 res.push_back(v2[j]);
10 j++;
11 }
12 }
13 while(i < v1.size()){
14 res.push_back(v1[i]);
15 i++;
16 }
17 while(j < v2.size()){
18 res.push_back(v2[j]);
19 j++;
20 }
21 return res;
22 }
9
Merge sort
Calculemos el órden de complejidad:
1 vector<int> mergesort(const vector<int> & v, int i, int j){
2 if(j - i == 0) // 4
3 return {}; // 1
4 if(j - i == 1) // 4
5 return {v[i]}; // 2
6
7 int med = (i+j)/2; // 4
8 vector<int> izq = mergesort(v, i, med); // T(n/2)
9 vector<int> der = mergesort(v, med, j); // T(n/2)
10
11 return merge(izq, der); // c*n
12 }
El tamaño de entrada n es j − i .
T (n) =
{
c si n = 0, n = 1,
2T (n/2) + cn si n > 1
10
Árbol de recursion
cn
c n
2
c n
4
...
c c
...
c c
c n
4
...
c c
...
c c
c n
2
c n
4
...
c c
...
c c
c n
4
...
. . .
...
c c
−→ cn
−→ cn
−→ cn
...
−→ cn
▶ Altura del árbol: log n + 1 niveles.
▶ Suma en cada nivel: cn.
▶ Total: cn log n + cn
▶ Propuesta: T (n) ∈ O(n log n)
11
Demostración por inducción
T (n) =
{
c si n = 0, n = 1,
2T (n/2) + cn si n > 1
▶ Queremos ver que T (n) ≤ k · (n log n), para algún k .
▶ Caso base:
▶ Con n = 0,
T (0) ≤ k · (0 log 0). No sirve, log 0 no está de�nido.
▶ Con n = 1,
T (1) ≤ k · (0 log 1)
c ≤ k · 0, no se cumple.
▶ Con n = 2,
T (2) ≤ k · (2 log 2)
2T (1) + 2c ≤ 2k
2c + 2c ≤ 2k
2c ≤ k
▶ Tomamos k = 2c y n0 = 2
12
Demostración por inducción
T (n) =
{
c si n = 0, n = 1,
2T (n/2) + cn si n > 1
▶ Caso inductivo: queremos ver que T (n) ≤ k · (n log n)
▶ Hipótesis inductiva: vale T (x) ≤ k · (x log x) para x < n.
▶ Sabemos que T (n) = 2T (n/2) + cn
▶ ≤ 2k(n/2) log(n/2) + cn, por hipótesis inductiva
▶ = kn log(n/2) + cn
▶ = kn log n − kn log 2+ cn
▶ = kn log n − kn + cn, ya que log 2 = 1.
▶ ≤ kn log n, siempre que k ≥ c .
▶ Vale, ya que habíamos tomado k = 2c .
13
Complejidad de Divide & Conquer general
Los problemas de Divide & Conquer tienen la siguiente recurrencia:
T (n) =
{
c si n = 0, n = 1,
aT (n/b) + f (n) si n > 1
(a subproblemas de tamaño n/b, f (n): costo de conquer)
Hay una técnica llemada Teorema Maestro (ver Cormen) que da una
�receta� para calcular la complejidad de recurrencias de esta forma.
Algunas recurrencias comunes y sus órdenes de complejidad
aT (n/a) + O(n) = O(n loga n) (a=2 es mergesort)
2T (n/2) + O(1) = O(n) (recorrer arbol binario)
T (n/2) + O(1) = O(log n) (búsqueda binaria)
14
Quicksort
123 7 388 41 2 280 50 59
▶ Elegir un elemento pivot y dividir el vector entre los menores y los
mayores al pivot.
7 41 2 50 59 123 388 280
▶ Ordenar cada partición recursivamente.
2 7 41 50 59 123 280 388
▶ Por cómo se hicieron las particiones, el vector ya queda ordenado:
2 7 41 50 59 123 280 388
15
Quicksort en C++
1 void quicksort(vector<int> & v, int d, int h){
2 if(d < h - 1){
3 int pos = dividir(v, d, h);
4 quicksort(v,d,pos);
5 quicksort(v,pos+1,h);
6 }
7 }
La función dividir:
▶ elige un pivot,
▶ particiona el subvector [d . . . h] y
▶ devuelve la posición del pivot.
16