x=n,y=0； while(x>=(y+1)*(y+1)) y++; y++执行次数，时间复杂度为多少？

x=n,y=0； while(x>=(y+1)*(y+1)) y++; y++执行次数，时间复杂度为多少？

相当于(y+1)^2<=n，在(y+1)^2<=n两边同时取根号，有y+1<=n^0.5，于是y<=n^0.5-1。因此问题变成while(y <= n^0.5 - 1) y++;因此y++的执行次数应该是n^0.5取整，时间复杂度为O(n^0.5)。


在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

相当于(y+1)^2<=n，在(y+1)^2<=n两边同时取根号，有y+1<=n^0.5，于是y<=n^0.5-1。因此问题变成while(y <= n^0.5 - 1) y++;因此y++的执行次数应该是n^0.5取整，时间复杂度为O(n^0.5)。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息