Question

数据结构，计算语句频度问题

k=0；
for（i=1；i<=n;i++）{
for(j=i;j<=n;j++)
k++;//这句的频度是多少，求计算的具体方法？
}

Answer 1

一、时间频度
定义：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中语句的执行次数称为语句频度或时间频度，记为T(n).

实例：计算1~100的和。在这里插入图片描述
注：第一种方式，T(n)=n+1，其中+1，是最后一次对条件判断，不成立然后退出循环。

1、忽略常数项
在这里插入图片描述
结论：
1）2n + 20 和 2n 随着 n 变大，执行曲线无限接近，20可以省略。
2）3n + 10 和 3n 随着 n 变大，执行曲线无限接近，10可以省略。

2、忽略低次项
在这里插入图片描述
结论：
1）2n2+3n+10 和 2n随着n变大，执行曲线无限接近，可以忽略 3n+10
2）n2+5n+20 和 2n2随着n变大，执行曲线无限接近，可以忽略5n+20

3、忽略系数
在这里插入图片描述
可见，在趋向“无穷”时，前两组的曲线近乎是一条重合的直线。后两组的执行曲线出现了分离。

结论：
1）随着n值变大，5n2+7n 和 3n2+2n，执行曲线重合，说明这种情况下，5和3都可以忽略。
2）但n3+5n 和 6n3+4n ，执行曲线分离，说明多少次是关键。

二、时间复杂度
1、定义：
一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于0的常数，则称f(n) 是T(n) 的同数量级函数。记作 T(n) = O( f(n) ) ，称 O( f(n) ) 为算法的渐近时间复杂度，简称时间复杂度。

注：T(n) 不同，但时间复杂度可能相同。
如T(n)=n2 +7n +6 和 T(n)=3n2+2n+2 它们的T(n)不同，但时间复杂度相同，都为O(n2).

2、计算方法
1）用常数 1 代替运行时间中的所有加法常数，T(n)=n2 + 7n + 6 => T(n)=n2 + 7n + 1
2）修改后的运行次数函数中，只保留最高阶项 T(n)=n2+7n+1 => T(n)=n2
3）去除最高阶项的系数 T(n) = n2 => T(n)= n2 => O(n2)

3、常见的时间复杂度
阶名 时间复杂度
常数阶 O(1)
对数阶 O(log2n)
线性阶 O(n)
线性对数阶 O(nlog2n)
平方阶 O(n2)
立方阶 O(n3)
k次方阶 O(nk)
指数阶 O(2n)
4、常见的时间复杂度对应的图
在这里插入图片描述
注：常见的算法时间复杂度由小到大依次为：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(n k) < O(nk) < O(2n)
随着问题规模 n 的不断增大，以上时间复杂度不断增大，算法的执行效率也越低。所以，我们要尽可能避免使用指数阶的算法。

1）常数阶：O(1)
在这里插入图片描述

2）线性阶：O(n)在这里插入图片描述
3）对数阶：O(log2n)
在这里插入图片描述

4）线性对数阶：O(nlogN)
在这里插入图片描述

5）平方阶：O(n2)
在这里插入图片描述

6）立方阶（O(n3)、K次方阶（O(nk)）
说明：参考上面的O(n2) 去理解，O(n3)相当于三层n循环，其它的类似。

5、平均时间复杂度和最坏时间复杂度
1）平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2）最坏情况下的时间复杂度称最坏时间复杂度。==一般讨论的时间复杂度都是最坏情况下的时间复杂度。==原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

Answer 2

数据结构，计算语句频度问题？i == n 时内循环只执行1次；
i == n-1时内循环执行2次；
……
i == 1时内循环执行n次。
所以k++的执行频度为1+2+...+n = n(n+1)/2。
最好写个程序验证一下。
另外对于这种循环变量直接关联的多重循环，其实有通用解法。涉及组合数学的东西先不介绍了。i=1时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。
i=2时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。
。。。。。。。。。。
i=n时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。
所以，k++的运行次数为 (n-1+1)*(n-1+1)=n^2
所以结果为O(n^2)

Answer 3

i=1时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。
i=2时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。
。。。。。。。。。。
i=n时，j从1运行到n，此时k++这句都是需要运行的，所以运行了n-1+1次。

所以，k++的运行次数为 (n-1+1)*(n-1+1)=n^2
所以结果为O(n^2)

Answer 4

i == n 时内循环只执行1次；
i == n-1时内循环执行2次；
……
i == 1时内循环执行n次。
所以k++的执行频度为1+2+...+n = n(n+1)/2。
最好写个程序验证一下。

另外对于这种循环变量直接关联的多重循环，其实有通用解法。涉及组合数学的东西先不介绍了。