Question

计算x=n;while(x>=(y+1)*(y+1))y++的时间复杂度？

Answer 1

相当于(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符号表述，不包括这个函数的低阶项和首项系数。
算法复杂度分为时间复杂度和空间复杂度。其作用：
时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

Answer 2

首先看循环条件，当x
<
(y+1)*(y+1)时退出循环
设y的初值为0，则第k次循环完后，y的值为k
于是循环的退出条件变为：(k+
1)*(k+
1)
>
n，也就是k
>
n^0.5
-
1，由于k为正整数，所以k为n^0.5
下取整
这样时间复杂度为O(n^0.5)，或者说O(根号n)