algs里分析ThreeSum算法的执行时间时用到了三层循环的执行次数，文章里只给了结论没有计算过程。不知道原理，只知道结果，不符合我的学习习惯，所以我用自己的方法尝试计算。下面是示例代码：
for (int i = 0; i < N; ++i) {
	for (int j = i + 1; j < N; ++j) {
		for (int k = j + 1 ; k < N; ++k) {
			// do something
		}
	}
} 

显而易见，最外层的循环的执行次数是$N$次，第二层循环次数是个等差数列：$N-1, N-2, N-3, ..., 3, 2, 1, 0$，所以第二层循环的执行次数是$\frac{N(N-1)}{2}$。第三层循环次数就不是那么直观了，可以先把i和j的值带入具体的值来分别计算第三层的循环次数，然后再分析下规律。
当$i=0, j\in[1, N-1]$时




i
j
第三层的循环次数




0
1
N-2


0
2
N-3


0
3
N-4


0
N-3
2


0
N-2
1


0
N-1
0


当$i=1, j\in[2, N-1]$时




i
j
第三层的循环次数




1
2
N-3


1
3
N-4


1
4
N-5


1
N-3
2


1
N-2
1


1
N-1
0


当$i=2, j\in[3, N-1]$时




i
j
第三层的循环次数




2
3
N-4


2
4
N-5


2
5
N-6


2
N-3
2


2
N-2
1


2
N-1
0


当$i=N-4, j\in[N-3, N-1]$时




i
j
第三层的循环次数




N-4
N-3
2


N-4
N-2
1


N-4
N-1
0


当$i=N-3, j\in[N-2, N-1]$时




i
j
第三层的循环次数




N-3
N-2
1


N-3
N-1
0


当$i=N-2, j\in[N-1, N-1]$时




i
j
第三层的循环次数




N-2
N-1
0


可以得出第三层循环的循环次数是与i相关的等差数列。




i
第三层的循环次数等差数列
第三层循环的循环次数和




0
N-2, N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-2)(N-1)}{2}$


1
N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-3)(N-2)}{2}$


2
N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-4)(N-3)}{2}$


…
…
…


N-4
2, 1, 0
3


N-3
1, 0
1


N-2
0
0


由等差数列求和公式$f(n)=\frac{n^2+n}{2}$可得第三层循环的循环次数和$sum(i)=\frac{(N-2-i)^2+(N-2-i)}{2},i\in[0, N-2]$，于是第三层循环的循环次数总和$\displaystyle \sum ^{N-2}_{i=0}sum(i)$

$=\displaystyle \sum ^{N-2}_{i=0}\frac{(N-2-i)^2+(N-2-i)}{2}$

$=\frac{(N-2)^2+(N-2)}{2}+\frac{(N-3)^2+(N-3)}{2}+\frac{(N-4)^2+(N-4)}{2}+...+\frac{(2)^2+(2)}{2}+\frac{(1)^2+(1)}{2}+\frac{(0)^2+(0)}{2}$

$=\frac{(N-2)^2+(N-3)^2+(N-4)^2+...+(2)^2+(1)^2+(0)^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}$
平方和公式$\displaystyle \sum ^{n}_{k=1}k^2=\frac{n(n+1)(2n+1)}{6}$和等差数列求和公式$f(n)=\frac{n^2+n}{2}$，所以

$\frac{(N-2)^2+(N-3)^2+(N-4)^2+...+(2)^2+(1)^2+(0)^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}$

$=\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2)^2+(N-2)}{2}}{2}$

为了方便计算，代入N-2=a

$\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2)^2+(N-2)}{2}}{2}$

$=\frac{\frac{a(a+1)(2a+1)}{6}+\frac{a^2+a}{2}}{2}$

$=\frac{\frac{a(a+1)(2a+1)+3a(a+1)}{6}}{2}$

$=\frac{\frac{(a+1)(2a^2+a+3a)}{6}}{2}$

$=\frac{a(a+1)(a+2)}{6}$

再代入a=N-2

$=\frac{a(a+1)(a+2)}{6}$

$=\frac{(N-2)(N-1)N}{6}$

所以

第三层循环的循环次数总和$\displaystyle \sum ^{N-2}_{i=0}sum(i)=\frac{(N-2)(N-1)N}{6}$

如果循环遍历list / tuple / sequence,则可以使用len(…)来推断循环执行的次数.但是当循环遍历迭代器时,你不能.
[为清晰起见更新：我正在考虑一次性使用有限迭代器,我想对项目进行计算并同时计算它们.]
我目前使用显式计数器变量,如下例所示：
def some_function(some_argument):
pass
some_iterator = iter("Hello world")
count = 0
for value in some_iterator:
some_function(value)
count += 1
print("Looped %i times" % count)
鉴于“Hello world”中有11个字符,
这里的预期产量是：
Looped 11 times
我还使用枚举(…)考虑了这个较短的替代方案,但我发现这并不清楚：
def some_function(some_argument):
pass
some_iterator = iter("Hello world")
count = 0  # Added for special case, see note below
for count, value in enumerate(some_iterator, start=1):
some_function(value)
print("Looped %i times" % count)
[更新供参考：@mata发现,如果迭代器为空,那么第二个例子在最初编写时会失败.插入count = 0解决了这个问题,或者我们可以使用for … else …结构来处理这个角落的情况.]
它不使用循环内的枚举(…)索引,而是将变量设置为循环计数几乎是一个副作用.对我来说这是非常不清楚的,所以我更喜欢第一个带有显式增量的版本.
是否有一种可接受的Pythonic方法(理想情况下是Python 3和Python 2代码)？

初识循环语句
在生活中，我们经常会遇到这样的事情
对大量的数字做数学运算，经常计算错误，很懊恼！！！
反复做同一件事情，经常枯燥无味，很烦躁！！！
我们可以把对大量的数字运算和反复做同一件事情的工作，交给计算机来做，计算机可是非常擅长完成重复的工作。
计算机程序通常会周而复始地重复同样的事情，在程序中成为循环。
在Python中有两种循环表达式
重复一定次数的循环，称为计数循环，用关键字for来表达，也称for循环
重复直到发生某种情况时结束的循环，称为条件循环，因为只要条件为真，这个循环一直进行下去，用关键字while来表达。
这节课我们主要讲解一下for循环
for循环语句
for循环语句的语法：
for iter_var in iterable: #冒号：不能少  suite_to_repeat #必须缩进4个空格
for是关键字
举个例子，反复输出5遍Hello World!!!
>>> for looper in [1, 2, 3, 4, 5]:... print('Hello World!!!')...Hello World!!!Hello World!!!Hello World!!!Hello World!!!Hello World!!!
[1, 2, 3, 4, 5]是列表(以后会讲到这个数据结构)，for会依次循环遍历这个列表。
for循环语句执行步骤：
1)首先将in后边的列表(中括号部分数据称为列表)中的第一元素1，并赋值给looper，这是looper变量的值就是数字”1”
2)执行循环体中的内容，也就是print语句
3)执行完循环体内容后，再从列表中读取第二个元素2，并赋值给looper，这是looper变量值就是数字2
4)再次执行循环体中的内容，也就是print语句
5)依次执行列表中的3、4、5
6)执行完5以后，列表所有的元素已经执行完毕，for循环执行完毕
每次循环在程序中成为一次迭代
再举一个例子：计算1 ~ 50数字的和
>>> sum = 0>>> for i in range(1, 51):... sum = sum + i...>>> print(sum)1275
range(1, 51)是1到50，不包含51，这是Python的函数，在讲到函数时，我们再详细的讲解。
通过Python计算1~50数字的和是不是很简单，4行代码就搞定了，程序的威力还不止这些，以后我们会慢慢体会。
while循环语句
while循环并不统计运行的循环次数，它会使用一个判断语句来确定什么时候停止循环，while循环又称为条件循环。
我们用while循环重新一遍计算1~50数字的和
>>> sum = 0>>> i = 1>>> while i < 51:... sum = sum + i... i = i + 1...>>> print(sum)1275
while循环计算1~50数字的和也是比较简单的
好了，就讲到这里，有什么问题可以在评论中留言或者关注我的公众号爱比特编程，再公众号里给留言，我会及时给你回答。

　　最近买了本《算法 第4版》打算看看算法，本来抱着割草的心理想快速过完第一章的基础知识然后去看红黑树神马的，结果居然被第一章的算法分析里一个小问题卡住了半天时间。决定记录一下。
问题描述　　
问题灰常简单，可以简单描述为：请问下面代码当n=100的时候，最终count等于多少（即最内层的for循环执行了多少次）。

    public static int count(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    count++;
                }
            }
        }
        return count;
    }

相信大多数人的第一感觉就是这还不简单，但是相信稍仔细看后，就会发现没那么简单。明显知道有个3次方，但是要想知道具体执行了多少次直接看真的看不出来。
求解
必须动笔了，我画出了下图：

可以看到我画出了3层循环，最下面是第3层的执行次数，因此要想知道count最终的值，就需要把最下面第3层所有的执行次数加起来。
分析图可以知道：
第三层的N-2 只出现在 第二层的N-1中
第三层的N-3 出现在第二层的 N-1和N-2 
第三层的N-4 出现在第二层的 N-1和N-2和N-3
...
第三层的1 出现在第二层除了1和0的其他次循环
依次类推，因此可以得出公式：
第三层总执行次数S=1*(N-2)+2*(N-3)+3*(N-4)+...+(N-2)*1
目前得出了一个公式，但是这个公式显然不能用来算100这样比较大的N。
因此需要想办法化简，观察到公式里的系数1、2、3...一直到(N-2)是等差数列，因此可以把S拆成N行，每行的系数都是1：
S=
(N-2)+(N-3)+(N-4)+...+1+    //(N-1)*(N-2)/2
          (N-3)+(N-4)+...+1+
                 +(N-4)+...+1+
                ... + 3 + 2 +1+    //6
                      ... + 2 +1+    //3
                                +1      //1
 
观察到每行都是等差数列，每行都可以用等差数列计算公式来表示，等差数列公式如下：
 
因此:

根据公式：（这个公式在文章最后会给出推导过程）

得：

推导完毕。
代入N=100，计算得161700，运行程序 调用count(100) 验证结果正确。
 
附 
最后附上中间用的公式12+22+32+...+n2的推导过程：
我们知道：(n+1)3=n3+3n2+3n+1，于是有：
23=13+3*12+3*1+1
33=23+3*22+3*2+1
...
(n+1)3=n3+3*n2+3*n+1
将各行相加，有：
23+33+...+(n+1)3=(13+23+...+n3)+3(12+22+...+n2)+3(1+2+...+n)+n

消去左右重复项，有
(n+1)3=13+3(12+22+...+n2)+3(1+2+...+n)+n
(n+1)3-13-3(1+n)n/2-n=3(12+22+...+n2)
解得：

总结
虽然因为一个小问题花了很多时间，但是我觉得是值得的，算法的一大核心就是分析算法的性能，如果连程序运行起来执行了多少次都搞不清楚，是没法去分析算法性能的。
对这个程序来说，有了这个公式，我们就可以很快计算出这个程序在N是一万、一百万的时候，程序将会执行count++的次数，而程序的运行时间和程序的运行次数是线性相关的，因此现在只要运行一次程序得到N=10的时候程序的运行时间，就可以手动计算N取任意数值的时候程序的预测运行时间。
转载于:https://www.cnblogs.com/sheeva/p/6497687.html