一道时间复杂度算法题
程序员文章站
2022-03-13 13:47:52
...
题目
int func(int n){
int i = 0,sum = 0;
while(sum < n)
sum += ++i;
return i;
}
A. O(logn) B. O(n^1/2) C. O(n) D. O(nlogn)
解题步骤
1.先找出基本操作,循环最深层的语句
2.确定问题规模并就算出关于n的函数式
分析
每次循环执行过程,i先自加1,再执行sum+=i
循环次数 | i值变化 | sum值变化 |
---|---|---|
1 | 由0变到1 | 0+1=1 |
2 | 由1变到2 | 1+2=3 |
3 | 由2变到3 | 3+3=6 |
··· | ··· | ··· |
假设循环体一共执行k次,
循环没执行一次,
i先自加1,所以 i = 1,2,3,4,5,···,k。
而 sum = 1+2+3+3+5+···+k = k*(k+1)/2
即此时 sum = k*(k+1)/2 >= n,(k+1)2 > 2n,得到k > (2n)1/2 - 1。
答案
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
选 B。
上一篇: 阶乘计算升级版