一个关于算法时间复杂度的问题
分析以下程序的时间复杂度。x=n; /*n>1*/
y=0;
while(x >= (y+1)*(y+1))
{
y=y+1; ①
}
解:这是一重循环的程序,while循环的循环次数为 根号下n,
所以,该程序段中语句①的频度是n,则程序段的时间复杂度是T(n)=O(根号下n)
问题:以上解答中是怎么算出while循环的循环次数为 根号下n的啊?小弟根基浅薄,各位大侠见笑了~~ --------------------编程问答-------------------- 根据循环条件
x>=(y+1)*(y+1)=Power(y+1, 2)
即
Sqrt(x) >= y+1
y是变量,从0开始,当然是Sqrt(x)次了,x等于n,所以是根号n次
--------------------编程问答--------------------
正解 --------------------编程问答-------------------- 十分感谢
补充:.NET技术 , C#