Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

16.12.2023

Дев-адвент 16: інтеграція регресії

Отже, вчора обрав влучні параметри функції ціни, щоб покривати графік відрізками регресії. Залишилось повернутися назад в головну програму та зробити робочу версію.

В чому проблема: я писав, що придумав, як уникнути кубічної складності при обчисленні розвʼязка. Поясню. Сам алгоритм динамічного програмування має квадратичну складність: один цикл для збільшення діапазону розвʼязку, а всередині — ще один, для перебору з розвʼязків для менших діапазонів.

Регресію я знайшов, як робити паралельно з внутрішнім циклом. Але оцінка якості регресії — теж цикл; необхідно порівняти значення в кожній точці. Виходить, що щоб оцінити, який розвʼязок найкращий, доведеться зробити ще один цикл — оцінки регресії.

Квадратична складність на декількох тисячах точок — не проблема для сучасного процесору, а кубічна — вже займає помітний час, декілька секунд.

Все це значить банально те, що розвʼязок потрібно зберігати, а не обчислювати наново щоразу. Бо минула вага є константою, тож і розбиття на відрізки теж. Хіба що у випадку редагування або імпорту старих даних доведеться обчислити повторно.

А решта мені подобається — модель нарешті математично акуратна.