欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一道时间复杂度算法题

程序员文章站 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。

相关标签: 数据结构和算法