Среднее арифметическое этих двух последовательностей равны.
Вычисляется разность между последовательностями следующим образом:
R = |a1-b1| + |a2-b2| + |a3-b3| +… + |an-bn|
Задача в том, возможно ли найти такой коэффициент k, домножив на который первую последовательность,
чтобы разница между последовательностями была минимальной.
т.е.
R = |k*a1-b1| + |k*a2-b2| + |k*a3-b3| +… + |k*an-bn|
т.е. нужно найти такой k, при котором R минимальна.
Другими словами, нужно подобрать такой масштабный коэффициент для первой последовательности, чтобы разница между последовательностями была минимальной.
Конечно, эта задача достаточно легко решается «двоичным поиском» (до определенной точности), но для этого нужно совершить некоторое количество вычислений R с разными k.
А можно ли как-то найти этот k не методом перебора?
1. R = a1*|k-b1/a1| + a2*|k-b2/a2| + a3|k3-b3/a3| +… + an|k-bn/an| (если ai=0 — то за скобки не выносим и нам это пофиг.
2. Очевидно, что такая функция кусочно-линейна относительна к на каждом из участков, к, для которых модули открываются с одинаковым знаком (предположим что а1/b1>b2/a2>...bn/an, если это не так — отсортируем что бы было так). Имеется ввиду что на участке [(ai/bi,(ai+1)/(bi+1)] функция будет линейна (!!! Это, в общем случае неверно для для (-inf,+inf).
3. Поскольку она линейна, то её минимум будет достигнут в одной из точек ai/bi.
4. ????? (перебираем все точки ai/bi)
5. Profit
Немного неверно про интервал [(ai/bi,(ai+1)/(bi+1)], потому что не факт, что элементы упорядочены таким образом.
В общем правильнее будет сказать так:
1. Функция R — кусочно линейная на всей области определения
2. Минимум конкретно такой функции R(k) будет достигаться в одной из точек недифференцируемости (точки перелома), они же являются числами ki = ai/bi.
3. В итоге, получая набор из n чисел ki, проверяем каждое из этих чисел и в итоге выбираем одно.
Сложность такого алгоритма (я правильно посчитал?) — линейная. Если число n слишком большое, то для выбора ki лучше использовать бинарный поиск, что сведет сложность до логарифмической.
Да, сложность линейная. Но мы уже говорили, что для бинарного поиска нужна монотонность, а функция не является монотонной на промежутке [min(ai/bi), max(ai/bi)].
metar, не смешно. Даже если n = 100 000 000 000, мой серверок на Intel Atom справится с задачей, нам ведь не нужно все хранить в ОП, можем спокойно читать из файла по 1 000 000 записей, обрабатывать, освобождать…
В бинарном поиске минимума сложность будет n*log(1/eps) — для каждой точки нам придется найти сумму n чисел. При переборе точек ai/bi придется потратить n*log(n) на сортировку — и дальше мы справимся за линейное время.
Если n=10^11, то будет сложно их нормально отсортировать. Но, конечно, возможно (например, раскидать в 1000 отсортированных файлов по 10^8 записей, а потом сортировать слиянием).
Брр, давайте разбираться. Продолжая опровергать бинарный поиск, скажу что при отсортированных ai/bi, R(ai/bi) отсортированным не будет, а ведь нам нужна именно его монотонность.
TheHorse, я писал независимо от необходимости размещения в памяти. Просто неизбежно придется данные считать, и бороться за O(log(N)) нет никакого смысла, ведь в наличии O(N) действий ввода. Конечно, может быть перед автором поставлена задача ответов на запросы изменения, и тогда мой мотив был не совсем чист. :-)
Поиск сделать можно, т.к. при отсортированных ai/bi, R(ai/bi) имеет соотношения:
R1 > R2 > Rmin < R3 < R4
т.е. график получается походим на «ломаную» параболу
DankoUAДаже раскрывать необязательно. Отсортируем пары (bi/ai,ai), возьмем s=-sum(ai), а потом на каждом шаге вычислять s+=2*ak. Как только перейдем через 0 — нашли минимум.
Какая производная? Функция недифференцируема в точках изгиба, а в других точках производная — константа.
Функцию придется выполнить n раз, гарантировано быстрее не получится. Раскрывать «заранее» модули — это тоже не выход — мы же меняем каждый раз к, и само значение модуля будет меняться. Если нужно ускорить процесс, можно задуматься о параллельных потоках, но тут могут вылезти очень большие накладные расходы на создание и поддержание потоков.
Если отсортировать по возрастанию bi/ai, возможно можно будет вычислять не n раз а меньше, т.к. как только сумма начнёт опять возрастать уже можно будет не считать. Но это надо еще математически показать.
Ну я вот опытным путем установил, что если построить график R(k), то он похож на параболу, т.е. сначала от точки к точке уменьшается, а потом увеличивается. Но действительно ли это так математически как проверить не знаю.
Если это действительно так, то вычислять можно будет не подряд все значения R(ki), до тех пор пока сумма не начнет расти, а бинарным поиском — при больших n значительно быстрее получится.
Во-первых, именно bi/ai — это те точки, в которых k*ai-bi обращается в 0. Во вторых, да — производная на каждом интервале (а не отрезке!) — константа, и эта функция (кусочно-постоянная) не убывает. И при поиске минимума нам нужно просто найти пару соседних интервалов, на левом из которых производная отрицательна, а на правом — положительна. Производная на интервале (ck,ck+1), где ck=bk/ak, равна -sum(i=1..n, ai)+2*sum(i=1..k,ai) — это нетрудно проверить (предполагается, что ck уже отсортированы), так что эту сумму для всех интервалов можно найти за один просмотр. И сумму модулей разностей в этом алгоритме мы вообще никогда не считаем.
double Min(double[]a,double[]b){
int len=a.Length;
int[] c=new int[len];
for(int i=0;i<len;i++) c[i]=i;
Array.Sort(c,(p,q)=>(b[p]*a[q]).CompareTo(a[p]*b[q]));
double s=0;
foreach(double p in a) s-=p;
foreach(int ind in c){
s+=2*a[ind];
if(s>=0) return b[ind]/a[ind];
}
return 0;
}
Числа a1..an, b1..bn заранее известны, но они могут быть совершенно случайными. И их количество n — тоже известно, но оно тоже может быть произвольным.
Ну в принципе, мы имеем функцию
R(k) = |k*a1-b1|+...+|k*a2-b2|
Или, например, возьмем частный случай:
R(k) = |k*3-2| + |k*1-2| + |k*4-1| + |k-5|
В таком случаем как-то можно найти Rmin(k)?
Я сейчас могу очень сильно ошибиться, но вроде это как первое, что приходит в голову.
Подобные задачи мы решали через производные.
То есть чтобы найти значение k, при которой функция будет иметь минимальное значение — мы берем первую производную.
R'(a, b) = |k*a1 — b1| +… + |k*an — bn| = R'(a)? R'(b) = |k — b1| +… + |k — bn|? |k * a1| +… + |k * an|
? — не уверен какое действие должно стоять.
Что в итоге — да ничего нового, потому что нужно и a, и b привести к какой-нибудь функции и получить одну неизвестную. А у вас их две.
Ну можно сказать что аналитически.
Числа a и b — случайные, длина n — случайная. Хочется найти формулу, подставляя в которую эти числа можно было бы получить Rmin(k)
И тогда нужно будет искать интервал, на котором функция не монотонная, и для этого интервала, с каким-то шагом проверять значения. Плюс обязательно проверить k = ai, bi. Когда найдется минимальное к, для него проверить k + epsilon, k — epsilon… Ну и так далее… Как-то так…
Ну не совсем что попало.
Если последовательности имеют одинаковое среднее арифметическое, то k лежит в пределах от 0 до 2.
И функция R(k) имеет вид, похожий на параболу с минимумом как раз в этих пределах. Так что там не совсем двоичный поиск, а поиск «методом вилки».
Давайте рассмотрим ваше утверждение про k — что оно лежит в пределах [0, 2].
Есть последовательность чисел А = {17, 90, 19}, B = {42, 42, 42}
Средние арифметические у них равны.
Начнем Rmin(k)= |17k-42| + |90k — 42| + |19k-42|
Так как у нас используется модуль числа, будем оценивать их.
При 17k — 42 > 0, все остальные модули тоже будут иметь положительное значение, тогда
17k — 42 + 90k — 42 + 19k — 42 = 126k — 126; Теперь найдем значение k, при котором данное уравнение минимально, не забывая. что 17k — 42 > 0, k > 42/16 ~ 2,47.
То есть уже утверждение, что k лежит в пределах [0,2] вызывает сомнение.
Утверждение «При 17k — 42 > 0, все остальные модули тоже будут иметь положительное значение» — не верно. Все остальные модули будут имет всегда не отрицательное значение
Простой
Простой
