метод наибольших квадратов :)

Я еще "могу" затянуть поясок на одну дырочку. =)))
Рассмотрим полином степени 0, т.е. y=const

Тогда 200 точек можно обработать за log(N) проходов быстрой или цифровой сортировками и выделить самый частый отсчет. что и требовалось.

 

Дубль

 

persicum
Согласны ли Вы то следующими утверждениями?
0) С телефона писать неудобно.
1) Сложность алгоритма поиска не может быть меньше O(N).
2) Таким упрощением Вы практически сводите задачу к одномерной.

 

KeSqueer
0) тогда носите с собой айПэд...
1) Согласитесь, ax+b это не самый простой полином =)))

 

А как Вы собираетесь найти самый частовстречающийся элемент массива за один пробег по массиву не заводя дикой памяти?

 

persicum
Никак.
Я к тому, что сложность быстрой сортировки N*log(N), а не просто log(N).

 

Я говорил не о вычислительной сложности, а о числе проходов по всему массиву.
Для быстрой сортировки оно log(N), ну а для цифровой так вообще 16 раз или 32 раза. =)))

т.е. для цифровой вычислительная сложность все-же O(N)

 

Впрочем, есть одна идея. Заключается в том, чтобы сгенерированные точки были не случайны, а являлись значениями некой непрерывной функции. Если такое допускается, попробую изложить подробнее вечером, когда будет доступ к компьютеру.
Правда, не гарантирую, что у нее есть право на существование.

 

[Del]

 

А если так:
Провести кривую(прямую) методом наименьших квадратов (МНК). Ту точку, которая сильнеее всего отклоняется, выкинуть. Провести опять. Выкинуть вторую точку. И так далее, пока ошибки будут меньше eps или равны нулю.
СойдетЬ? Перебора нет =)))

 

Не выйдет. Возьми, к примеру, набор точек {-2,2},{-1,1},{0,0},{1,1},{2,2}. Если методом МНК провести через них прямую, ты выкинешь нулевую точку, а обе прямые, проходящие через 3 точки, проходят через неё.

 

Ravager
Гон! Какая из прямых более правильная, с наклоном в +1 или в -1?

 

Проверка показала, что для точек -2,2 -1,1 0,0 1,1 2,2 3,3 максимально отклоняющейся от прямой точкой будет таки 0,0 =((( Странно, ведь есть же двухкратное превышение количества правильных точек над неправильными?

 

Новый опыт =)))
Если использовать на простой МНК, а с весами 1/(1+abs(y)), то тогда главной выпадающей точкой будет уже -2,2 :P