Переборное решение. Алгоритм
Вычислить конкретное значение можно с помощью одного оператора, использующего метод sum
Организовать переборное решение можно простым перебором всех возможных значений L,M,R
и вычислением значения для выбранной тройки. Сложность такого решения будет O(N
4),
где N - размер списка.
Сложность можно понизить до O(N
3), если использовать префиксные суммы.
Тогда вычисление конкретного значения будет O(1)
Пусть Items - список со значениями, N=len(Items). Определим список P_items, положив:
- P_items[0]=0
- P_items[L]=sum(Items[:L])
Тогда sum(S
(L,R))=P_items[R+1]-P_items[L]
В следующем фрагменте представлено переборное решение.
Для заданного N, программа генерирует случайный набор чисел размера N (числа по модулю не превосходят 100)
вычисляет ответ. Также выводит процессорное время работы программы