时间复杂度例题与解析_时间复杂度的计算例题及答案

作者：盐析白兔 | 2024-08-12 06:28:17

踩

时间复杂度的计算例题及答案

1.分析以下时间复杂度

void fun(int n)
{
int i=0,s=0;
while(s<n)
{
++i;
s=s+i;
}
}
答：n为规模，基本操作语句是++i和s=s+i，while循环处当s>=n不符合条件停止，假设执行m次结束，i=1,2,3..依次渐加，i只影响s值，主要看s， s1 =1, s2 =1+2=3, s3 =1+2+3=6，... sm =1+2+3+...+m=m(m+1)/2 ,正解答案中给出，m(m+1)/2+k=n (k起修正作用的常数)，也可大致口算m≈ √n ,则时间复杂度为O( √n )

2、设n是描述问题规模的正整数，则下列程序片段的时间复杂度是（）

i=n*n;
while(i!=1)
i=i/2;
A. O(㏒2n)

B. O(n)

C. O(√n)

D. O(n＾2)

【解析】
答案：A

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/968139