计算x=n;while(x>=(y+1)*(y+1))y++的时间复杂度?
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/27 12:27:28
![计算x=n;while(x>=(y+1)*(y+1))y++的时间复杂度?](/uploads/image/z/12503950-70-0.jpg?t=%E8%AE%A1%E7%AE%97x%3Dn%3Bwhile%28x%3E%3D%28y%2B1%29%2A%28y%2B1%29%29y%2B%2B%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%3F)
计算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)