Ограничение записей весового вектора

Question

Позвольте v = (v(1), ..., v(n)) быть вектором положительных чисел, таких как v(1) + ... + v(n) = 1. Пусть l > 0 такой, что 1/l ≤ n и предположим, что v(k) > l для некоторых k.

Рассмотрим следующий алгоритм:

1. Помещенный v(k) = lk для каждого такого, что v(k) > l.
2. Нормализация v, То есть, положить v = v/(v(1) + ... + v(n)).

Легко видеть, что повторное применение этого алгоритма v сходится к некоторому вектору w таким образом, что для каждого w(k) ≤ lk и w(1) + ... w(k) = 1. Моя цель - найти быстрый алгоритм, который вычисляет точное значение w.

Идея заменяет каждую запись v, которая больше l, на l, а затем нормализует остальную часть записей. Это приводит к следующему алгоритму:

1. Пусть I = (i(1), ..., i(m)) будет список индексов, таких, что v(k) > l тогда и только тогда, когда k принадлежит I и J = (j(1), ..., j(n-m)) его дополнение, то есть, список индексов, таких, что v(k) ≥ l тогда и только если k принадлежит к J.
2. Положить v(i(k)) = l на каждые 1 ≤ k ≤ m.
3. Положить v = (1 - m * l) * v(j(k))/(v(j(1)) + ... + v(j(k))) на каждые 1 ≤ k ≤ n-m.

Проблема заключается в том, что могут существовать некоторые k такие, что v(k) < l перед применением алгоритма и v(k) > l после его применения. Таким образом, по-прежнему необходимо применять его повторно. Тем не менее он сходится к w не более чем в n шагах.

Применяя предыдущий алгоритм неоднократно эквивалентно замене m крупнейших вхождений v по l, а затем нормализуя остальную часть записи, для определенного выбора m. Есть ли быстрый способ найти значение m или вектор w, возможно, в линейном времени?

Answer 1

Мой инстинкт кишки (часто неправильно!) Заключается в том, что лучшее, что вы можете сделать это, - это O(n log n) раз. Для того, чтобы сделать это в O(n log n) время: - (. Это требует обход массива один раз, поэтому O(n) временной сложности)

1. Put массива в порядке возрастания (временная сложность O(n log n) например, сортировка слияние)
2. Сделать массив кумулятивных сумм
3. для каждого m, теперь легко решить в постоянная время ли массив, полученный путем замены крупнейших m чисел 1 и нормализацией является то, что вы хотите.(Сумма всех чисел будет одним из суммарных итогов плюс m, поэтому вам просто нужно проверить значение (m+1) -го наибольшего значения, деленное на эту сумму. Поэтому найти m на этом этапе требует линейного поиска, опять O(n) .

Поэтому общая временная сложность этого алгоритма является o(n log n).