Question

给出下面几个C语言程序段的时间复杂度。要求写出计算过程 ，谢谢了，在线等。

给出下面几个C语言程序段的时间复杂度。要求写出计算过程
(1) int i=1;
while (i<=n)
i=i*5;
(2) x=n; y=0; //n为整数
while (x>=(y+1)*(y+1))
y++;
(3) for (i=1;i<=n;i++)
if (3*i<=n)
for(j=3*i;j<=n;j++)
{ x=x+1; y=3*x+2;}

Answer 1

求时间复杂度只需找出执行次数最多的那条语句。
对于第一个，设执行次数为k,则i最终等于k^5=n; 解出k即可；
对于第二个，设执行次数为k，则最终有k^2=n;解出k；
对于第三个，if语句执行n/3次，单独看里面的for执行（n-n/3）次，结合if语句，则最终有
（n-n/3）*n/3 ，时间复杂度一眼便知

追问

非常感谢你的答案，能给我具体的步骤吗？

Answer 2

1、主要操作是i = i * 5和i<=n，设循环次数为x，则5^x <= n，因此x <= log5(n)，其中5是底数，因此时间复杂度为O(log5(n))。
2、主要操作在while循环中，设循环执行次数为x，则x^2<= n，x <= sqrt(n)，因此时间复杂度为O(sqrt(n))。
3、主要是看内循环执行的次数，当i=1时，内循环执行n-3次i=2时，内循环执行n-6次，所以总的执行次数是(n-3*1)+(n-3*2)+(n-3*3)+...+(n-3*n/3)。总的项数为n/3，因此总次数为n*(n/3)-3*(1+2+...+n/3)=(n^2 - 3n)/6。因此时间复杂度为O(n^2)