Transcript InversionCountingx

What NetFlix wants: To accurately guess
what movies you will enjoy.
What NetFlix knows:
1. What other movies you have enjoyed
2. What movies other people have enjoyed
Yours
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Grosse Point Blank
Hunger Games
Lord of the Rings
Momento
Serenity
The Spanish Prisoner
Dangerous Liaisons
12 Monkeys
The Sting
The Dark Knight
Person of Impeccable Taste
1. Grosse Point Blank
2. Shawshank Redemption
3. Hunger Games
4. Lord of the Rings
5. Momento
6. Serenity
7. The Spanish Prisoner
8. Dangerous Liaisons
9. 12 Monkeys
10. The Sting
11. The Dark Knight
Yours
1. Grosse Point Blank
2. Lord of the Rings
3. Momento
4. Serenity
5. The Spanish Prisoner
6. Dangerous Liaisons
7. 12 Monkeys
8. The Sting
9. The Dark Knight
Person of Very Good Taste
1. Grosse Point Blank
2. Shawshank Redemption
3. Momento
4. Serenity
5. The Spanish Prisoner
6. Dangerous Liaisons
7. 12 Monkeys
8. Lord of the Rings
9. The Sting
10. The Dark Knight
Yours
1. Grosse Point Blank
2. Lord of the Rings
3. Momento
4. Serenity
5. The Spanish Prisoner
6. Dangerous Liaisons
7. 12 Monkeys
8. The Sting
9. The Dark Night
Person of Decent Taste
1. Grosse Point Blank
2. Lord of the Rings
3. Momento
4. Serenity
5. Dangerous Liaisons
6. Shawshank Redemption
7. 12 Monkeys
8. The Sting
9. The Dark Night
How do we match your preferences
to others?
How do we identify those with
“similar” tastes?
Notice: not a well-defined problem
(as stated)
We can measure the similarity of a list by counting the
number of inversions
Inversion: Any pair (a,b) where a appears before b in one
list and after b in another
As integers:
• Number objects from 1 to n based on one list
• Translates numbers to other lists
• Pair i,j form an inversion if i < j and A[i] > A[j]
1
2
3
4
5
7
8
Yours
Grosse Point Blank
Shawshank Redemption
Lord of the Rings
Momento
Serenity
Dangerous Liaisons
12 Monkeys
10The Dark Knight
9 The Sting
6 Harry Potter III
Person of Impeccable Taste
1. Grosse Point Blank
2. Shawshank Redemption
3. Lord of the Rings
4. Momento
5. Serenity
6. Harry Potter III
7. Dangerous Liaisons
8. 12 Monkeys
9. The Sting
10. The Dark Knight
1
2 3 4 5 7
8 10 9 6
1
2 3 4 5 6 7
8 9 10
#inversions = # cross points
What is the runtime of the naive algorithm
for inversion counting (check every pair)?
1.
2.
3.
4.
5.
O(n2)
O(n log n)
O(n)
O(log n)
O(1)
3
3
1
7
7 4 5 9 8 10 2 6
Need to compare every
split pair
Total: 3 + 7 + ???
T(n) = 2T(n/2) + O(n2)
T(n) = (n2 )
31 31 4
7 4
5 5
7 2
9 6
8 10
8 9
2 10
6
1
2 3 4 5 6 7 8 9 10
Total split pairs: 4
0
5
MergeAndCount(array A, int i, int j, int mid)
(1)
array tmp; count  0
(2)
p1  i, p2  mid+1, k  0
(3)
while (p1  mid && p2  j)
(4)
if (A[p1]  A[p2])
(5)
tmp[k++] = A[p1++]
(6)
else
(7)
count  count + (mid-p1+1)
(8)
tmp[k++] = A[p2++]
(9)
while (p1  mid)
(10)
tmp[k++] = A[p1++]
(11)
while (p2  j)
(12)
tmp[j++] = A[p2++]
(133) return count
int CountAndSort(Array A, int i, int j)
(1) if i  j
(2) return 0
(3) int mid  (i+j)/2
(4) return CountAndSort(A, i, mid) +
CountAndSort(A, mid+1, j) +
CountAndMerge(A, i, j)
T(n) = 2T(n/2) + O(n)
What is the runtime for this algorithm?
1.
2.
3.
4.
5.
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
T(n) = 2T(n/2) + O(n)
T(n) = (n log n)
Proof: Identical to merge-sort