2021年数据结构课程设计--问题 A: 复杂度分析(Ⅰ)

问题 A: 复杂度分析(Ⅰ)

题目描述

请分析如下代码

for(i=1;i<n;i++)
  for(j=1;j<i;j++)
    for(k=1;k<j;k++)
      printf("\n");
1
2
3
4

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

输入

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

输出

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

样例输入

6
1

样例输出

10 15
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 .
1