2021年数据结构课程设计--问题B：复杂度分析(Ⅱ)_问题 b: 复杂度分析(ⅱ)

问题B：复杂度分析(Ⅱ)

题目描述

有如下代码段(n为正整数)：

i=1;
while(i++<n)
{
  j=1;
  while(j++<i)
  {
   	k=1;
    while(k++<j)
    {
     	printf("\n");
    }
  }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13

问printf语句共执行了几次？这段代码执行完以后i+j+k值为多少？

输入

由多行组成，每行一个整数n, 1<= n <= 3000

输出

对每一行输入，输出对应的一行，包括空格分开的两个整数，分别代表printf语句的执行次数以及代码执行完以后i+j+k的值, 如果值不确定,输出"RANDOM"取代值的位置

样例输入

3
1

样例输出

4 12
1

解题过程

理论知识

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）

大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 // 数学归纳法得
1
2

方法二

直接暴力推算法，最后p就是语句执行频度（缺点是如果n过大时执行时间超级长）
此方法主要可以用来验证公式法所得的结果是否准确

#include <stdio.h>
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 %d\n", p, i + j +k);
        i = 1;
        p = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最终解决代码

注：本部分代码为作者独立设计，这是第一次AC通过的代码，后期优化后的代码在下面的实验报告里。

#include<stdio.h>
#include<math.h>
int main()
{
	long long n;
	while (scanf("%lld", &n)!=EOF)
	{
		if (n > 1)
		{
			n = n - 1;//以下这个通项是在 n 大于等于 2 的情况下求得的，因此 n - 1 为代入公式的 n
			printf("%lld %lld\n", (n * n * n + 3 * n * n + 2 * n) / 6, 3 * n + 6);//数学计算-数列求和及通项
		}
		else
			printf("0 RANDOM\n");
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

提示（关键）

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 RANDOM\n");
			continue;
		}
		cnt = sum = 0;
 		while (i++ < n)
        {
            j = 1;
            while (j++ < i)
            {
                k = 1;
                while (k++ < j)
                {
                    p++;
                }
            }
        }
		sum = i + j + k;
		printf("%lld %d\n", cnt, sum);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

O（n^3）的算法，超时！

	while (scanf("%d", &n) != EOF)
	 {
		printf("%lld ", ((long long)(n - 1)) * (n - 2) * (n - 3) / 6);
		if (n > 0)
			printf("%d\n", 3 * n + 6);
		else
			puts("RANDOM");
	}
1
2
3
4
5
6
7
8

O（1）的算法，完美通过！耗时 0ms

算法分析

注：含时间复杂度和空间复杂度分析等
本题的时间与空间复杂度分析包含在上一部分当中。

项目小结

注：含对这个项目的心得体会及改进建议等
心得体会：解决小规模问题可以简单模拟，解决大规模的复杂问题应该探索其中规律，复杂问题简单化，降维解决问题，寻找更高效的解决办法。
内存超限，输出超限等：要注意while循环实现多组输入时要添加截止条件（！=EOF || ！=0），尽管输入的 n 不超过3000，但三层循环后可能为3000的立方，超过了int型的范围，因此使用long long型。

声明：本文由博主原创，请同学们自己借鉴思考后，独立完成课程设计的有关题目，请勿直接复制粘贴，祝同学们课程设计顺利（课程设计后的期末考试也要加油哦！）

如果发现本文有那些错误和问题请及时私信博主，感谢各位大佬批评指正！

看都看了，点个赞再走吧！