题目

数据结构的时间复杂度 i=0,s=0； while(s

提问时间：2020-12-12

答案

其实数学上的定义我也不用说了,简单来说就是通过求出该算法执行次数呗,通过观察while的条件,可以知道s和n作为循环条件,假设n是5050的话,是不是就是从1加到100啊,那不就是100次吗,就是设（上面的k和n写反了,呵呵,不好意思）n=1+2+...+k=(k*(k+1)/2)=(k^2+k)/2-->k*(k+1)=2*n-->k^2>k*(k+1)=2*n-->k>(2*n)^(1/2)（就是k>根号2*n）,所以去掉常数2^(1/2)（就是根号2）,时间复杂度就是O(n^1/2)（既根号n）