Как расчитать Big O при генерации статистики по значениям?

Question

[qiGuar]

Столкнулся со следующим заданием:
Имеется веб сервис с нсколькими endpointами.
Имеется набор чисел и нужно вывести статистику по ним при запросе на один из endpointов: максимальное число, минимальное, среднее значением, сколько всего чисел.
Сложность состоит в том, что данный запрос должен обрабатываться за константное время и память (constant time and memory o(1)).
Пока что идея только иметь джобу, которая запускается каждую секунду и считает статистику по имеющимся числам, а запрос к endpoint будет возвращать уже посчитанные значения.
Тут есть нюанс: если в течении одной секунды добавится новое число и будет запрос на статистику, то данные вернутся некорректные, тк джоба не пересчитает значение.
Подскажите, пожалуйста, что я упускаю и как подойти к решению проблемы, чтобы было константное время выполнения?

Comments

[Роман]

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

1. При инициализации производим расчет статики (вычисляем максимальное число max, минимальное min, среднее значением mx, сколько всего чисел count)
2. при каждом добавлении нового числа num пересчитываем их так (псевдокод):

max = max<num?num:max
min = min>num?num:min
mx = (mx*count+num)/(count+1)
count++

3. при обращении за статикой выдаем рассчитанные max min mx и count

Answer 1

[Wataru]

Мне кажется, надо статистику пересчитывать за константное время при вводе каждого нового числа. При запросе выдвавть последнюю статистику. Если часть чисел задана изначально, то придется подсчитать статистику для них за O(n), по другому никак - ведь все числа придется хоть раз просмотреть.