> 数学 >
计算x=n;while(x>=(y+1)*(y+1))y++的时间复杂度?
人气:157 ℃ 时间:2020-02-05 05:55:42
解答
首先看循环条件,当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)明白了,谢谢!
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版