1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

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

Тема в разделе "WASM.A&O", создана пользователем persicum, 30 ноя 2010.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Я еще "могу" затянуть поясок на одну дырочку. =)))
    Рассмотрим полином степени 0, т.е. y=const

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

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Дубль
     
  3. KeSqueer

    KeSqueer Сергей

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

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    KeSqueer
    0) тогда носите с собой айПэд...
    1) Согласитесь, ax+b это не самый простой полином =)))
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А как Вы собираетесь найти самый частовстречающийся элемент массива за один пробег по массиву не заводя дикой памяти?
     
  6. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    persicum
    Никак.
    Я к тому, что сложность быстрой сортировки N*log(N), а не просто log(N).
     
  7. persicum

    persicum New Member

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

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

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Впрочем, есть одна идея. Заключается в том, чтобы сгенерированные точки были не случайны, а являлись значениями некой непрерывной функции. Если такое допускается, попробую изложить подробнее вечером, когда будет доступ к компьютеру.
    Правда, не гарантирую, что у нее есть право на существование.
     
  9. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
  10. persicum

    persicum New Member

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

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    Не выйдет. Возьми, к примеру, набор точек {-2,2},{-1,1},{0,0},{1,1},{2,2}. Если методом МНК провести через них прямую, ты выкинешь нулевую точку, а обе прямые, проходящие через 3 точки, проходят через неё.
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Ravager
    Гон! Какая из прямых более правильная, с наклоном в +1 или в -1?
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Проверка показала, что для точек -2,2 -1,1 0,0 1,1 2,2 3,3 максимально отклоняющейся от прямой точкой будет таки 0,0 =((( Странно, ведь есть же двухкратное превышение количества правильных точек над неправильными?
     
  14. persicum

    persicum New Member

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