Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия Последняя версия Следующая версия справа и слева | ||
research:prob_median_petya [2018/09/09 01:36] nikita [Задание 1] |
research:prob_median_petya [2018/09/15 00:03] nikita |
||
---|---|---|---|
Строка 1: | Строка 1: | ||
====== Вычисление взвешенной медианы для Пети, фотографирующего филинов ====== | ====== Вычисление взвешенной медианы для Пети, фотографирующего филинов ====== | ||
- | + | <note warning> | |
+ | |||
+ | Тому, кто уже успел его сдать, баллы зачтены.</ | ||
===== Задание 1 ===== | ===== Задание 1 ===== | ||
Петя -- любитель живой природы. Он пытается измерить размах крыльев обыкновенного филина. Для этого он сфотографировал филина в полёте $N$ раз, после чего на каждой фотографии провёл измерение $x_i$ требуемого параметра, | Петя -- любитель живой природы. Он пытается измерить размах крыльев обыкновенного филина. Для этого он сфотографировал филина в полёте $N$ раз, после чего на каждой фотографии провёл измерение $x_i$ требуемого параметра, | ||
Строка 10: | Строка 12: | ||
Трудоемкость (по порядку) не больше $N^2$: | Трудоемкость (по порядку) не больше $N^2$: | ||
Трудоемкость (по порядку) не больше $N \log N$: 2 курс – 20 баллов, | Трудоемкость (по порядку) не больше $N \log N$: 2 курс – 20 баллов, | ||
- | Трудоемкость (по порядку) в среднем линейная по $N$, с объяснением: | + | Трудоемкость (по порядку) в среднем линейная по $N$ или детерминированная $O(N)$, с объяснением: |
==== Подготовка ==== | ==== Подготовка ==== |