Есть ли быстрый алгоритм, который может вычислитьпола суммирующий алгоритм
? p, q, k, l, A и B - целые числа. Под «быстрым» я подразумеваю, что он должен быть намного быстрее, чем простой цикл O (B-A).
Относительно: Если положить k = 0, то существует алгоритм O (log (p) + log (q)), который решает проблему.
Вот решение во времени O (q). (Я полагаю, что p и q являются относительно простыми, иначе вы должны просто сначала сократить фракцию).
Для каждого целого г в диапазоне [A, A + Q) можно определить значение
floor [p*(A+r)/q + k/l]
Пусть это будет п (г). Тогда вы можете повторно выразить свою сумму в качестве
sum_{r=0}^{q} sum_{y=0}^{y_max(r)} (n(r)+p*y),
где
y_max(r) = floor[ (B-A)/q ]
Теперь каждая внутренняя сумма может быть вычислена в O (1), как это полностью явное, и вы получите O (Q) в Всего.
Итак, хотя 'p' и' q' являются целыми числами, вы не хотите целочисленного деления? Если коэффициенты 'p/q' и' k/l' являются константами, нет смысла использовать их в вашей нотации с большим O. –
сложность, которую вы просите, не имеет смысла: вы добавляете N элементов N = B-A; p, q, k, l не влияют на количество шагов, предпринятых для вычисления конечной суммы, следовательно, они не влияют на сложность. Возможно, то, что вы хотите, лучше чем O (n), что и дает вам формула. – Pandrei
@ Ивайло Странджев: есть функция пола, которая мешает вам делать это – Zuza