※ 引述《fcouple (皇家典藏20年礼炮)》之铭言：
: 各位，不管考上的，还在努力的资讯前辈们，大家好。
: 小弟在研究103年高考资料结构第七题时，碰到了一些问题，带上来和大家讨论，
: 也期盼能够抛砖引玉，若有观念不正确的地方，请前辈用力鞭打。
: 第一题，
: sum=0
: for(i=0; i<2*n; i++)
: for(j=0; j<i; j++)
: sum++;
: 可以计算出 sum 的执行次数为 (2n-1)*2n / 2
: 其 Big-O是 O(n^2)
: 但为何Θ也是Θ(n^2)，这点我比较不解。
: 我反问自己，那Ω notation又是多少呢? 回答不出来，该不会也是 Ω(n^2) 吧?
: 若如此，O、Ω、Θ 差在那? 不是应该要有“上限、下限、相等”的概念在里面吗?
: O、Ω、Θ 的定义看了又看，就是无法从定义去推出 Θ(n^2)
设f(n)=O(g(n))且f(n)=Ω(g(n))
by Big-O定义，得
f(n) <= c_1 x g(n)
by Big-Ω定义，得
f(n) >= c_2 x g(n)
可写成
c_2 x g(n) <= f(n) <= c_1 x g(n)
与Θ定义一样
f(n)恰好贴在g(n)的紧密上限，又恰好贴在g(n)的紧密下限，所以f(n)与g(n)复杂度相等
: 第二题，
: sum=0
: for(i=0; i<2*n; i++)
: for(j=0; j<i*i; j++)
: for(k=1; k<j; k++)
: if(j%i == 1)
: sum++;
: 考场上，有没有“一定的程序、方法”去找出这种“非常复杂”的巢状循环执行次数。
有“一定的程序、方法”
就是直接代数字
: 我在想，补习班写解答的也没那么神，应该有先用电脑去跑程式，用 trace 的方式去
补习班写解答应该也是照程式码直接代数字求解
: print 次数，然后再回推答案。但是考试时，没有电脑可以用呀。
: 每次遇到这种复杂的巢状循环，就是等死，心有不甘。
: 忙读书，无法一一回谢。先谢谢参与讨论的人，你会更加进步的。
: 祝金榜题名。
代数字
i j k j%i sum
0 不执行
1 0 不执行
2 0 不执行
2 1 不执行
2 2 1 0不执行
2 3 1 1 1
2 3 2 1 2 i=2时，sum共计执行2次
3 2 1 2不执行
3 3 1 0不执行
3 3 2 0不执行
3 4 1 1 3
3 4 2 1 4
3 4 3 1 5 (.......小计3次)
3 5 1 2不执行
...
3 6 1 0不执行
...
3 7 1 1 6
3 7 2 1 7
3 7 3 1 8
3 7 4 1 9
3 7 5 1 10
3 7 6 1 11 (.......小计6次) i=3时，sum共计执行3+6次
3 8 1 2不执行
...
4 2 1 2不执行
4 3 1 3不执行
...
4 4 1 0不执行
...
4 5 1 1 12
4 5 2 1 13
4 5 3 1 14
4 5 4 1 15 (........小计4次)
4 6 1 2不执行
...
4 7 1 3不执行
...
4 8 1 0不执行
...
4 9 1 1 16
4 9 2 1 17
4 9 3 1 18
4 9 4 1 19
4 9 5 1 20
4 9 6 1 21
4 9 7 1 22
4 9 8 1 23 (........小计8次)
4 10 1 2不执行
...
4 11 1 3不执行
...
4 12 1 0不执行
...
4 13 1 1 24
4 13 2 1 25
...
4 13 12 1 35 (........小计12次) i=4时，sum共计执行4+8+12次
4 14 1 2不执行
...
4 15 1 3不执行
...
归纳可得，每个i，sum共计执行i+2i+3i+...+(i-1)i次
i,2i,3i,...,(i-1)i为等差数列(固定相差i)
代入等差公式，得
[i+(i-1)i] x (i-1) / 2 化简为
(i^3 - i^2) / 2 ....每个i，sum执行次数
i范围从0到2n-1，对i加总
2n-1 2n-1 2n-1
Σ (i^3-i^2) /2 = 1/2( Σ i^3 -Σ i^2)
i=0 i=0 i=0
=1/2 { {[0+(2n-1)]2n / 2}^2 - n(n+1)(2n+1)/6 }
...(请自行化简)
n最大4次方，可得Θ(n^4)