Самый быстрый алгоритм для подведения итогов чисел до [закрытого] N

Попробуй ...

Где n - максимальное целое число, которое нужно суммировать.

Сумма равна (n * (N + 1)) / 2

int sum (int n) { return (n <0? N * (- n + 1) / 2 + 1: n * (n + 1) / 2); }

Чтобы завершить приведенные выше ответы, вот как вы доказываете формулу (пример для положительного целого числа, но принцип тот же для отрицаний или любого арифметического набора, что и Void указал).

Просто напишите набор два раза, как показано ниже, и добавьте числа:

  1+   2+   3+ ... n-2+ n-1+   n   = sum(1..n)     : n terms from 1 to n
+ n+ n-1+ n-2+ ...   3+   2+   1   = sum(n..1)     : the same n terms in reverse order
--------------------------------
n+1+ n+1+ n+1+ ... n+1+ n+1+ n+1   = 2 * sum(1..n) : n times n+1

n * (n+1) / 2 = sum(1..n)

вы слышали о последовательности и сериалах? "Быстрый" код, который вам нужен - это сумма арифметических рядов от 1 до N .. погуглите .. фактически откройте книгу по математике ..

Для борьбы с целочисленным переполнением я бы использовал следующую функцию:

sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );

Формула, которую вы ищете, представляет собой более общую форму формулы, опубликованной в нескольких ответах на ваш вопрос, которая представляет собой арифметический ряд / прогрессию с разницей фактором 1 . Из Википедии это следующее:

Вышеупомянутая формула будет обрабатывать отрицательные числа до тех пор, пока m всегда меньше, чем n . Например, чтобы получить сумму от 1 до -2, установите m на -2 и n на 1, то есть сумму от -2 до 1. Это приведет к следующему:

(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.

, что является ожидаемым результатом.

если | n | достаточно мала, поисковая таблица будет самой быстрой.

или используя кеш, сначала выполните поиск в кеше, если не можете найти запись, затем вычислите сумму, используя n * (n + 1) / 2 (если n положительно), и запишите результат в кеш.

sum = N * (N + 1) / 2