数据结构中关于语句频度计算

2024-11-30 08:42:24

推荐回答（3个）

回答（1）：

1、首先时间复杂度定义，如下图所示。

2、在大多数情况下，原操作是最深层循环内的语句的原操作，他的执行次数和包含他的语句的频度相同。

3、以上三例都含有基本操作“x++”但频度各有不同。

4、时间复杂度分别为，常量阶、线性阶、平方阶。

5、最后计算时间复杂度，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项的阶数）。

回答（2）：

具体有递归公式
An=An-1+n*(n+1)/2 //计算次数
A1=1

因此An=1/2(∑(n^2)+∑n)
=1/2(n(n+1)(2n+1)/6+n(n+1)/2)
=n(n+1)(n+2)/6

所以时间复杂度是O(n^3)

回答（3）：

[(m-1)*(2+m)]/2