IVl*_*lad 30
如果N是积极的:int sum = N*(N+1)/2;
如果N是否定的:int tempN = -N; int sum = 1 + tempN*(tempN+1)/2 * (-1);.
- 没有解释*如何*这是有效的？我会试一试:"N/2"找到0到N之间所有数字的平均值.我们从1开始,所以将其改为"(N + 1)/ 2".现在我们有了平均值,我们只需要乘以序列中的值数(N)(实际上是N-1(起始值)+1(1到2包含2个值,而不是2-1 = 1) ),但是N-1 + 1 = N).所以`N*((N + 1)/ 2)`,减少='N*(N + 1)/ 2`. (4认同)
- "如果N是负数",最后需要一个"+ 1".1 + 0 + -1 + -2 = -2,而不是-3. (2认同)
- @Dave:是的,你应该总是执行过早的优化,因为它确实有所作为,编译器永远不够聪明,无法自己解决这个问题.还要注意它可能更快,因为它不会做同样的事情(你想要`>> 1`). (2认同)
flo*_*rin 24
sum = N * (N + 1) / 2
- 但那只是O(1)! (18认同)
- 你总是可以硬编码-32,768到+32,767的总和值.更少的周期:D (2认同)
- 我不认为它适用于负数.如果N是-3,则该式给出3但-3 + -2 + -1 + 0 + 1 = -5 (2认同)
- @gmatt是正确的,这实际上是'O(log N)`,除非你限制`N`的值,在这种情况下,naïve循环也是'O(1)`. (2认同)
- 如果我对维基百科的理解是正确的,那么Schönhage-Strassen算法(它似乎是发现最快,实际可用的算法)会给这个问题带来时间复杂度:O(log N log log N log log log N) (2认同)
Voi*_*oid 18
您正在寻找的公式是一个在多个答案张贴到你的问题,这是一个更一般的形式等差数列/级数有差别的因素1.来自维基百科,它是以下内容:
只要m始终小于n,上述公式将处理负数.例如,要将总和从1到-2,将m设置为-2,将n设置为1,即从-2到1之和.这样做会导致:
(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.
这是预期的结果.
- +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)
| 归档时间： |
|
| 查看次数： |
6345 次 |
| 最近记录： |