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

泠然xc 1年前 已收到1个回答 举报
赞

life003 春芽

共回答了14个问题采纳率：71.4% 举报

首先看循环条件,当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)

1年前 追问

4

泠然xc 举报

明白了，谢谢！
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.027 s. - webmaster@yulucn.com