Разница между верхним N и верхним N допускает дублирование:
input: 1, 9, 7, 9, 5, 10, 7
top 3: 10, 9, 9
top 3 allow duplicates: 10, 9, 9, 7, 7
Алгоритм с верхним N является интуитивно понятным.Все машины запускают алгоритм N верхнего уровня, а один компьютер получает все результаты вместе и запускает алгоритм N верхнего уровня.
machine A: 1,9,
machine B: 9, 5,10, 7, 7
step 1: each machine runs top 3
machine A: 9, 1
machine B: 10, 9, 7
step 2: machine C get all results and runs top N
input to machine C: 9, 1, 10, 9, 7
run top 3 again: 10, 9, 9
Алгоритм Top N, выполняемый на каждой машине, может быть реализован с использованием кучи, а временная сложность будет O (MlogN) (M = количество входных строк)
Может применяться верхний N, разрешающий дублированиеаналогичный алгоритм распределения, но я не знаю, как это доказать.и я не могу придумать контрпример.
machine A: 1,9
machine B: 9, 5,10, 7, 7
step 1: each machine runs top 3 allow duplicates
machine A: 9, 1
machine B: 10, 9, 7, 7
step 2: machine C get all results and runs top N allow duplicates
input to machine C: 9, 1, 10, 9, 7, 7
run top 3 again: 10, 9, 9,7,7
В верхнем N разрешить повторяющиеся запуски на каждом компьютере можно реализовать с использованием heap + map (для дедупликации), а временная сложность также будет O (MlogN) (M = # входных строк)
Как доказать, что это правильно?Или какой встречный пример доказывает, что он неверен?