问题B：复杂度分析(Ⅱ)
题目描述
有如下代码段(n为正整数)：
i=1;
while(i++<n)
{
j=1;
while(j++<i)
{
k=1;
while(k++<j)
{
printf("n");
}
}
}
问printf语句共执行了几次？这段代码执行完以后i+j+k值为多少？
输入
由多行组成，每行一个整数n, 1<= n <= 3000
输出
对每一行输入，输出对应的一行，包括空格分开的两个整数，分别代表printf语句的执行次数以及代码执行完以后i+j+k的值, 如果值不确定,输出"RANDOM"取代值的位置
样例输入
3
样例输出
4 12
解题过程
理论知识
算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）
大O表示法
像前面用O( )来体现算法时间复杂度的记法，我们称之为大O表示法。
算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。
大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶，那么如何推导出f(n)的值呢？我们接着来看推导大O阶的方法。
推导大O阶
推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：
1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
思路
方法一
利用数学归纳法和数列求通项的有关过程，求取三阶for循环递推算法的时间复杂度（语句执行频度），经计算可知，当你小于等于3时，语句的执行频度为0，当n大于等于4的时候，对应的语句执行频度为
n = 4 5 6 7 8 9 10 ...... n
O() = 1 4 10 20 35 56 84 ...... (n^3+3*n^2+2*n)/6 // 数学归纳法得
方法二
直接暴力推算法，最后p就是语句执行频度（缺点是如果n过大时执行时间超级长）
此方法主要可以用来验证公式法所得的结果是否准确
#include
int main()
{
int i = 1;
int n, j = 1, k = 1, p = 0;
while (scanf("%d", &n) != EOF)
{
while (i++ < n)
{
j = 1;
while (j++ < i)
{
k = 1;
while (k++ < j)
{
p++;
}
}
}
printf("%d %dn", p, i + j +k);
i = 1;
p = 0;
}
}
最终解决代码
注：本部分代码为作者独立设计，这是第一次AC通过的代码，后期优化后的代码在下面的实验报告里。
#include
#include
int main()
{
long long n;
while (scanf("%lld", &n)!=EOF)
{
if (n > 1)
{
n = n - 1;//以下这个通项是在 n 大于等于 2 的情况下求得的，因此 n - 1 为代入公式的 n
printf("%lld %lldn", (n * n * n + 3 * n * n + 2 * n) / 6, 3 * n + 6);//数学计算-数列求和及通项
}
else
printf("0 RANDOMn");
}
return 0;
}
提示（关键）
1）关于求解时间复杂度
while语句的时间复杂度一般与log函数有关，与上一题（问题A：时间复杂度（I））相比较来说时间复杂度并不相同，之所以公式相同是因为这两题中的for与while循环嵌套均符合数列的相同数学归纳原则（我对本题的算法只有粗浅的理解，为了不误导大家，不在算法层面给出直接的解读），在for循环中，采用了局部变量作为判断条件，在while循环中则要借助一个辅助语句作为其截止的判断条件。在for循环的通项中n被以n-3带入，而在while中n则以n-1带入。
2）关于求解i+j+k
就题论题的来说，for循环将在i达到所判断的条件（即i<n）时截止，而截止后的i将不会在进行后面的i++，而while（i++<n）则代表着i先进行一次自增再与条件比较，比较后不符合则截止，这也就是为什么造成了i+j+k结果的后移，当i=2时，进行i++操作，使得i=3<3不成立，循环截止，同理再向下递推当导：i=3时，j则递推一位变成4，而k最终则变成5，因此最终i+j+k的结果就是（n+n+1+n+2）=（3*n+3)，因此最初的n被更改为n-1，所以将n=n+1带入方程中，得到了最终的结果。
解释：为什么会出现RANDOM的情况？
在n <= 2时，i，j，k最初的定义都是int i，j，k；因此未进行初始化，for语句的赋值语句要执行后i，j，k才有值，因此在n <= 2时，总有至少一个循环变量是没有被进行赋值的，因此会出现RANDOM。
3）关于运算的优先级
造成以上差别的关键因素之一是运输的优先级（尤其是在while中是先++还是先比较）在这里就不详细介绍了，同学们可以在其他博主的博文中学习。
课程设计实验报告（HNUST）
注：实验报告的模板格式采用HNUST提供给2020级计算机学院&潇湘学院计算机专业的模板格式，下面的实验报告内容包括原创的算法分析过程，还有部分引用和借鉴的有关理论和基础知识部分，欢迎各位同学参考，也欢迎各位同学对实验报告中的问题提出宝贵的意见和建议！
项目名称
问题B：复杂度分析(Ⅱ)
内容和目的
计算指定代码语句的语句执行频度以及对循环变量求值；为了提高对算法时间复杂度的理解以及对while与for循环的理解，提高对算法流程的分析和理解能力。
第一部分：项目分析与总体设计
注：含背景知识或基本原理、或模块介绍、ADT设计等、设计步骤等
/抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）/
背景知识：
算法的时间复杂度：在进行算法分析时，语句总的执行次数T(n)是关于问题n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记：T(n)=O(f(n))。他表示随问题n的增加，算法执行时间的增长率和f(n)的增长率相同，f(n)是问题规模的某个函数。
一般情况：随着输入规模n的增加，T(n)增加最慢的算法为最优算法。
语句执行频度：在数据结构中，频度是指一个定义变量在它的函数中，并且是它在执行到该段语句为止时，这个定义变量在函数总共执行基本操作的次数。
基本原理：
多层嵌套循环的语句执行频度符合一定的数学规律，可以通过数学方法求解。对于小规模的数据，也可以通过最简单的计数方式直接统计语句的执行频度。
对于循环变量的最终值求解，for 和 while 语句的判断条件和计算方式等综合因素具体分析就可以得到结果。
模块介绍：
本算法主要由两部分组成，第一部分是基础语句执行（含输入输出模块），第二部分是计数计算模块。
ADT设计：
此项目不涉及ADT设计。
设计步骤：
1）先用最简单的计数计算方法解决小规模数据问题。
2）对于中等规模的数据可以利用数学方法降次解决。
3）对于更大更具有挑战性规模的数据，可以通过推导数学公式来解决。
数据结构和算法实现
注：含主要的数据结构、程序流程图、算法实现等
主要数据结构：
本题根据算法规模的大小，分为循环结构和顺序结构（这不是数据结构），本题不涉及复杂的数据结构设计。
程序流程图：
略
实现算法：
注：本部分代码仅包含关键部分。
/*最低效的设计算法*/
while (scanf("%d", &n) != EOF)
{
if (n == 1 || n == 2)
{
printf("0 RANDOMn");
continue;
}
cnt = sum = 0;
while (i++ < n)
{
j = 1;
while (j++ < i)
{
k = 1;
while (k++ < j)
{
p++;
}
}
}
sum = i + j + k;
printf("%lld %dn", cnt, sum);
O（n^3）的算法，超时！
while (scanf("%d", &n) != EOF)
{
printf("%lld ", ((long long)(n - 1)) * (n - 2) * (n - 3) / 6);
if (n > 0)
printf("%dn", 3 * n + 6);
else
puts("RANDOM");
}
O（1）的算法，完美通过！耗时 0ms
算法分析
注：含时间复杂度和空间复杂度分析等
本题的时间与空间复杂度分析包含在上一部分当中。
项目小结
注：含对这个项目的心得体会及改进建议等
心得体会：解决小规模问题可以简单模拟，解决大规模的复杂问题应该探索其中规律，复杂问题简单化，降维解决问题，寻找更高效的解决办法。
内存超限，输出超限等：要注意while循环实现多组输入时要添加截止条件（！=EOF || ！=0），尽管输入的 n 不超过3000，但三层循环后可能为3000的立方，超过了int型的范围，因此使用long long型。
