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

2024年11月30日 08:42

有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