目的
我们在讨论一些方法复杂度的时候，特别是循环实现的算法，需要根据具体的循环情况来找出渐进时间复杂度的函数。其实这个过程就是求一个数列的求和公式。
举一实例
为什么是上面这么说呢？我们看一个简单的实例就知道了：
private static void sample(int n) {
for (int i = 1; i < n; i <<= 1) { //注：i <<= 1表示i = i *2
for (int j = 0; j < i; j++) {
// Some Code
}
}
}
我们直接开始计算Some Code位置每次执行的次数，假设我们的n=17，我们最外层的循环次数为5次，i分别为1、2、4、8，16，那么Some Code位置对应每一趟执行的次数就为下表：
所以Some Code位置每趟执行的次数为2的第几趟次方，所以现在的重点是找出n这种情况下，要执行多少趟了，结论很容易得出：
注意趟数只能为整数。现在我们就能计算这个程序的执行次数了，也就是求2的第几趟次方为通项的通项式和：
那么这个数量的求和公式是什么呢？这就是今天我们要讨论的，求一个数列求和公式的方法。常见的方法如下，介绍完这些方法后，我们再来求上面这个数列的求和公式
公式法
公式法的意思是什么呢，就是直接用已有的公式，常见的一些数列的求和公式我们可以记住，因为有的时候，我们其他一些数列的求和公式还需要使用它们，常见的如下：
错项相减
这种方式主要针对等差*等比的数列：1q^0、2q^1、3q^2、4q^3、5q^4……我们要求出这个数列的求和公式就可以用这种方法。详细步骤如下：
这里我们就用到了上面已有的、等比数列的求和公式
裂项相消法
这种方法主要从通项式下手，分解通项式，然后再组合，使之能消除一些项，以达到我们得出求和公式的目的，如有下面特征的一些通项公式的数列，就可以使用这个方法：
例如上面的(3)的过程为：
倒序相加法
这种方式主要要利用到数列对称位置上两个数的和相等的规律，常见的我们的等差数列求和就可以用这种方式：
① 1+2+3+……+(n-2)+(n-1)+n
倒序后
② n+(n-1)+(n-2)+……+3+2+1
① + ② = (n+1)+(n+1)+(n+1)+……+(n+1) = n(n+1)
所以S = n(n+1) / 2
分组求和法
分组求和法是对于一些由等差、等比或者常见数列组成的数列，可以将它拆分后分别求和，最后再求总和的方法，这个方法很好理解，就不举例了，这里再一次说明记住常见数列求和公式的重要性
求最初的那个数列的求和公式
其实这个数列就是一个等比数列，只是数列的长度不是为n，而是为log2^(n-1)，带入公式即可，最后得出：
S = 2n-3
因此该方法的时间复杂度为O(n)，而不是直观的O(n^2)
