@qiGuar

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

Столкнулся со следующим заданием:
Имеется веб сервис с нсколькими endpointами.
Имеется набор чисел и нужно вывести статистику по ним при запросе на один из endpointов: максимальное число, минимальное, среднее значением, сколько всего чисел.
Сложность состоит в том, что данный запрос должен обрабатываться за константное время и память (constant time and memory o(1)).
Пока что идея только иметь джобу, которая запускается каждую секунду и считает статистику по имеющимся числам, а запрос к endpoint будет возвращать уже посчитанные значения.
Тут есть нюанс: если в течении одной секунды добавится новое число и будет запрос на статистику, то данные вернутся некорректные, тк джоба не пересчитает значение.
Подскажите, пожалуйста, что я упускаю и как подойти к решению проблемы, чтобы было константное время выполнения?
  • Вопрос задан
  • 68 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Мне кажется, надо статистику пересчитывать за константное время при вводе каждого нового числа. При запросе выдвавть последнюю статистику. Если часть чисел задана изначально, то придется подсчитать статистику для них за O(n), по другому никак - ведь все числа придется хоть раз просмотреть.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы