PDF de programación - Análisis y Diseño de Algoritmos - Comparación de preferencias

Comparación de preferencias
Comparación de preferencias
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Comparación de preferencias
Comparación de preferencias

comparar laslas preferencias

preferencias de un
de un

intenta comparar

Un Un sitiositio web web intenta
usuario
usuario con
 El El usuario
 La La aplicación

con laslas de de otros
otros::
usuario establece
aplicación web web consulta

encontrar
encontrar usuarios
encontrar
encontrar usuarios

usuarios con
usuarios con

establece un ranking de n

un ranking de n productos
productos..

base de datos
consulta susu base de
con gustos
con gustos
gustos similares
gustos similares
similares..
similares..

datos parapara

similitud: :
Medida
Medida de de similitud
inversiones” entre dos rankings:
Número
Número de “de “inversiones
” entre dos rankings:
Ranking A: 1, 2, …, n.
: 1, 2, …, n.
 Ranking A
 Ranking B: a
Ranking B: a11, a, a22, …, a
 ii y j y j están

invertidos sisi ii < j < j peropero aaii > > aajj..

están invertidos

, …, ann..

11

Comparación de preferencias
Comparación de preferencias

Productos

P1 P2 P3 P4 P5
1
5
5
1
5
1

3
4
4

2
3
3

4
2
2

A
B
B

Inversiones

3-2, 4-2
3-2, 4-2

fuerza bruta
Algoritmo
Algoritmo porpor fuerza
todos los pares (
Comprobar todos
Comprobar
ΘΘ(n(n22))

los pares (i,ji,j))

bruta: :

22

Comparación de preferencias
Comparación de preferencias

Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”

 División

División: :
Dividir
Dividir la la listalista de de productos
recursivamente
recursivamente el el número
recursivamente
recursivamente el el número

productos en dos
número de de inversiones
número de de inversiones

contar
mitades y y contar
cada mitadmitad..
cada mitadmitad..

inversiones en en cada
inversiones en en cada

en dos mitades

 Combinación
Combinación::
Contar
Contar laslas inversiones
diferentes
diferentes y y devolver

inversiones en en laslas queque aaii y y aajj están
de 3 cantidades
cantidades..

devolver la la suma

suma de 3

están en en mitades
mitades

33

Comparación de preferencias
Comparación de preferencias

Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”

1 5

4 8 10 2

6 9

12 11 3 7

1 5
1 5

4 8 10 2
4 8 10 2

6 9
6 9

5 inversiones

12 11 3 7
12 11 3 7
8 inversiones

División: 2T(n / 2)
División: 2T(n / 2)

9 inversiones entre una mitad y la otra:
5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7

Combinación: ???

Total = 5 + 8 + 9 = 22.

Comparación de preferencias
Comparación de preferencias

Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
Combinación
Combinación

 Asumiendo
Asumiendo queque cada
contabilizan
contabilizan
contabilizan laslas inversiones
contabilizan laslas inversiones
mitades diferentes
están
están en en mitades

cada mitadmitad estáestá ordenada
inversiones en en laslas queque aaii y y aajj
inversiones en en laslas queque aaii y y aajj

diferentes. .

ordenada, se
, se

 A A continuación

continuación, se

, se mezclan

mezclan laslas dos dos mitades

mitades parapara

devolver
devolver un un conjunto

conjunto ordenado
ordenado..

44

55

Comparación de preferencias
Comparación de preferencias

Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
Combinación
Combinación

3 7

10 14 18 19

2 11

16 17 23 25

6
6

3
3

2
2

2
2

0
0

0
0

13 inversiones: 6 + 3 + 2 + 2 + 0 + 0

Conteo: O(n)

2 3

7 10 11 14

16 17

18 19 23 25

Mezcla: O(n)

T(n) ≤ T n / 2



(

)+ T n /2

(



)+ O(n) ⇒ T(n) = O(n log n)

Comparación de preferencias
Comparación de preferencias

Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
Implementación
Implementación

Sort-and-Count(L)
{

if (L.length==1)
if (L.length==1)

return (0, L);

Dividir la lista en dos mitades A y B
(rA, A) ←←←← Sort-and-Count(A)
(rB, B) ←←←← Sort-and-Count(B)
(rB, L) ←←←← Merge-and-Count(A, B)

return (rA + rB + r, L);

}

66

77

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 6

3 7

10 14 18 19

2 11
3
6

Total:

16 17 23 25
2
0

0

2

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 6

3 7

10 14 18 19

2 11
6
3

2

Total: 6

16 17 23 25
2
0

0

2

88

99

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 6

3 7

10 14 18 19

2 11
6
3

2

Total: 6

16 17 23 25
2
0

2

0

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 5

3 7

10 14 18 19

2 11
6
3

2 3

Total: 6

16 17 23 25
2
0

0

2

1010

1111

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 4

3 7

10 14 18 19

2 11
6
3

2 3

7

Total: 6

16 17 23 25
2
0

0

2

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 3

3 7

10 14 18 19

2 11
6
3

2 3

7 10

Total: 6

16 17 23 25
2
0

0

2

1212

1313

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 3

3 7

10 14 18 19

2 11
3
6

2 3

7 10 11

Total: 6 + 3

16 17 23 25
2
0

2

0

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 2

3 7

10 14 18 19

2 11
3
6

2 3

7 10 11 14

Total: 6 + 3

16 17 23 25
2
0

2

0

1414

1515

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 2

3 7

10 14 18 19

2 11
3
6

2 3

7 10 11 14

16

Total: 6 + 3 + 2

16 17 23 25
2
0

0

2

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 2

3 7

10 14 18 19

2 11
3
6

2 3

7 10 11 14

16 17

Total: 6 + 3 + 2 + 2

16 17 23 25
2
0

2

0

1616

1717

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 1

3 7

10 14 18 19

2 11
3
6

16 17 23 25
2
0

0

2

2 3

7 10 11 14

16 17

18

Total: 6 + 3 + 2 + 2

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 0

3 7

10 14 18 19

2 11
3
6

16 17 23 25
2
0

0

2

2 3

7 10 11 14

16 17

18 19

Total: 6 + 3 + 2 + 2

1818

1919

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 0

3 7

10 14 18 19

2 11
3
6

16 17 23 25
2
0

2

0

2 3

7 10 11 14

16 17

18 19 23

Total: 6 + 3 + 2 + 2 + 0

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 0

3 7

10 14 18 19

2 11
3
6

16 17 23 25
2
0

0

2

2 3

7 10 11 14

16 17

18 19 23 25

Total: 6 + 3 + 2 + 2 + 0 + 0

2020

2121

Comparación de preferencias
Comparación de preferencias

MergeMerge & & Count
Count

i = 0

3 7

10 14 18 19

2 11
3
6

16 17 23 25
2
0

0

2

2 3

7 10 11 14

16 17

18 19 23 25

Total: 6 + 3 + 2 + 2 + 0 + 0 = 13

2222