i=0;s=0; while(s<n) { i++; s=s+i; } T(n)=O(n) 时间复杂度是??

2025-04-02 02:33:38
推荐回答(1个)
回答1:

按照循环条件,退出时有s>=n
设第x 次循环后退出循环,此时i = x, s= x(x+1)/2
代入得到x(x+1)>=2n,解方程得到x=(-1+根号(1+8n))/2上取整
因此时间复杂度为O(n^0.5),或者说O(根号n)