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

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

计算x=n;while(x>=(y+1)*(y+1))y++的时间复杂度?
首先看循环条件,当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)