数据结构的时间复杂度问题

2024-12-01 18:35:17

推荐回答（4个）

回答1：

一楼的算法不合理，详细如下：
void fun(int n)
{
int i,j,x,y; //(3次)
for (i=1;i<=n;i++) //(n次)
if (3*i<=n) //(n次)
for (j=3*i;j<=n;j++) //(n(n+1)/6次)
{
x++;y=3*x+2; //(n(n-1)/6次)
}
}
该程序的时间复杂度T(n)=n(n-1)/6+(n(n+1)/6+n+n+1=4n-1=O(n^2)

回答2：

只运行外围循环的O(n*2/3)
运行2层循环的，总次数是个等差数列的和，能算，忽略系数后是O(n*n)

所以结果是O(n*n)
其实复杂度是取极限，2层循环一般都是O(n*n)

回答3：

2层for循环，时间复杂度为O（n^2)

回答4：