Andy_U

Читайте: https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B8%D...

Почитайте про кластерный анализ. Ну или возьмите готовый модуль: sklearn.cluster

У вас задача на тему топологической сортировки: По ссылке stackoverflow.com/questions/4620100/partial-order-... есть код на питоне, котрый останавливается, как только все что можно, отсортировывается. Т.е. когда остаются лишь циклы. Вот и вам надо имплементировать что-то типа этого. Вроде бы сложность O(сумма нод + сумма ребер графа). Плюс сложность построения самого графа.

Уважаемый автор, попробуйте вот этот вариант (Python 3.8) на вашем компьютере. Результат вас удивит.

import time
import sys
from functools import lru_cache


@lru_cache(5000000)
def calc(number: int) -> int:

    if number == 1:
        return 0
    elif number % 2 == 0:
        iterations = calc(number//2)+1
    else:
        iterations = calc(3*number+1)+1

    return iterations


if __name__ == '__main__':

    sys.setrecursionlimit(2000)
    start = time.process_time()
    max_num, num = 0, 0

    for i in range(1, 1000000+1):
        if (cur_num := calc(i)) > max_num:
            max_num, num = cur_num, i

    print('n =', num, 'iterations =', max_num+1, 'time =', time.process_time()-start, 'sec')

Если поменять декоратор на

@numba.njit()

то будет еще чуть быстрее.

Инсталируйте пакет mpmath, повторите ваш расчет с его использованием (задав там много-много знаков) и без и сравните результаты. Если формулы простые, это будет быстро. А потом, если грабли найдутся, ищите конкретные причины.

Посмотрите на пакет Shapely. Там есть операция "раздувания" фигур. Всякая логика тоже есть.

Ну, на первый вопрос ответить просто. Кусочно линейная интерполяция удовлетворяет всем вашим указанным в вопросе требованиям :). А если таки учесть "дополнения и приложения", то надо на том из двух участков, где наклон прямой больше (пусть это будет, например, левый подинтервал), сделать интерполяцию функцией

y = a+b*x+c*x**2

такой что:

1) Значение параболы в x1 равно y1
2) Значение функции в x2 равно y2
3) Производная функции в x2 равно наклону прямой в правом подинтервале.

Доказывать мне лень, но кажется очевидным, что такая парабола будет монотонной на подинтервале.

P.S. Если прямая на правом подинтервале не устраивает, ее можно тоже чуть изогнуть.

P.P.S. Однако, такой (и любой подобный) алгоритм не даст решения для большего числа точек, поскольку первая производная будет иметь разрывы, которые Вас, как я понял, не устраивают. А при этом условии даже для четырех точек легко придумать пример, чтобы монотонность была, но обязательно с перегибом - взять 4 точки на S-образной кривой (две поближе к краям)... И как не крутись, без перегиба в центральной области не обойтись.

Вообще-то, это задача по теории обслуживания... Есть случайное потребление, есть случайные поставки со случайными задержками, есть стоимость хранения, есть "штрафы" за отстутствие товара на складе, товар портится, если не использован в течение некоторого срока, и т.д. и т.п.

Т.е., я бы начал разбираться с предметной областью, а потом уже инструменты моделирования и оптимизации выбирал. Хотя бы разобрался, каков критерий успешности решения задачи "определение потребности в закупках лек. препаратов..."

Если вы знаете количество чисел, их сумму и сумму их квадратов, то можете вычислить и среднее, и дисперсию. Любой учебник по мат.статистике и/или стат.обработке данных Вам поможет. Единственно, что надо следить за накоплением ошибок округления и возможным переполнением при суммировании.