首页 > 试题广场 >

下列函数的时间复杂度是 int test(int n) {

[单选题]
下列函数的时间复杂度是
int test(int n) {
    int i = 0, sum = 0;  
    while(sum < n)
        sum += ++i;  
    return i;
} 
  • O(log2n)
  • O(n)
  • O(n^0.5)
  • O(nlog2n)
查看正确选项
添加回答
pein531头像 pein531
sum要加到n，根据高斯求和公式，从0加到i得sum=(0+i)*(i+1)/2=i*(i+1)/2=n，一共操作了i+1次，n为i的平方量级，所以复杂度为O(n^0.5)
编辑于 2021-09-25 12:27:43 回复(0)
提交观点

问题信息

golang工程师 PHP工程师 虾皮信息 Java工程师 信息技术岗
上传者：小小
难度：
1条回答 769浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号