Какова сложность времени выполнения парного суммирования?

Question

Я прочитал, что numpy использует парное суммирование в качестве алгоритма по умолчанию для вычисления суммы (что также подтверждается одним из запросов на получение в репозитории numpy github)

Так для фрагмента, подобного следующему и в целом:

data = np.ones((1000,1000))
sum = np.sum(data)

print(sum)

Какова сложность времени выполнения попарного суммирования?Поскольку он следует жадному подходу, подобному divide and conquer, он должен быть в масштабе log, но я не уверен в точном уравнении.

Answer 1

Парное суммирование выполняет то же количество сложений, что и наивное суммирование.

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

По этой причине предпочтительнее парное суммирование.