关于算法时间复杂度的一些问题

yiyan • • 问答 • 55 阅读

void fun(int n)

{
int i=0, s=0;
while(s<n)
{
i++;
s=s+i;;
}
}

该算法的时间复杂度是多少，如何计算的

回答

O(logn) :
假设t次结束循环 s= (1+2+3+...+t)=(1+t)*t/2>=n
去掉常数项: t^2 >= n
t >= log(n)
时间复杂度 O(logn)

以上是关于算法时间复杂度的一些问题的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>