Вычисление взвешенной медианы для Пети, фотографирующего филинов
Warning
Обратите внимание: это задание больше не принимается, так как его решение описано в книге Т. Кормена и пр. "Алгоритмы: построение и анализ".
Тому, кто уже успел его сдать, баллы зачтены.
Задание 1¶
Петя – любитель живой природы. Он пытается измерить размах крыльев обыкновенного филина. Для этого он сфотографировал филина в полёте \$N\$ раз, после чего на каждой фотографии провёл измерение \$x_i\$ требуемого параметра, \$1 \le i \le N\$. Однако фотографии получились смазанными, некоторые сильно, некоторые нет. Фоторедактор на компьютере Пети умеет для каждой фотографии определять её “вес” \$w_i\$ в выборке: чем чётче фотография (то есть, “вес” \$w_i\$ больше), тем вероятнее, что измерение лежит близко к настоящему значению. Петя обратился за помощью к своему научному руководителю ВВ. Тот предложил ему оценить размах крыльев филина с помощью взвешенного метода наименьших абсолютных отклонений: \$m_{opt} = \text{argmin}_{m} \sum_{1 \le i \le N} w_i |m - x_i|\$. Требуется найти \$m_{opt}\$. Петю устроит любое \$m_{opt}\$, на котором достигается минимум. Важна быстрота подсчета \$m_{opt}\$. Порядок трудоемкости метода надо обосновать.
Баллы¶
Баллы зависят от трудоемкости по \$N\$.
Любая трудоемкость: 2 курс - 10 баллов, 1 курс – 20 баллов.
Трудоемкость (по порядку) не больше \$N^2\$: 2 курс – 15 баллов, 1 курс – 30 баллов.
Трудоемкость (по порядку) не больше \$N \log N\$: 2 курс – 20 баллов, 1 курс – 40 баллов.
Трудоемкость (по порядку) в среднем линейная по \$N\$ или детерминированная \$O(N)\$, с объяснением: 2 курс – 40 баллов, 1 курс – 80 баллов.
Подготовка¶
Нужно написать программу, где на вход поступает \$N\$, затем \$N\$ измерений размаха \$x_i\$ и положительных весов \$w_i\$. Можно для простоты считать, что \$w_i\$ и \$x_i\$ целочисленные. Результатом программы является найденное \$m_{opt}\$. Задача на то, чтобы придумать, как можно минимизировать нужную функцию. Чтобы программа работала для большого \$N\$, нужно воспользоваться свойствами конкретной целевой функции.
Tip
Для начала нужно понять, почему при равных весах $w_i=1$ минимум достигается на выборочной медиане.
Руководитель¶
Никита Звонарев