下列程序段的时间复杂度是
int count = 0; i,j; for(i=1;i*i<=n; i++) for(j=1;j<=i; j++) count++;
A. logn B.n C.nlogn D.n^2
这段代码的时间复杂度是 B 选项,...
用户登录可进行刷题及查看答案
这段代码的时间复杂度是 B 选项,即 O (n)。
下面来详细分析:
i*i < n
j < i
内层循环的总执行次数为:0 + 1 + 2 + ... + ($\sqrt{n}$ - 1)。利用等差数列求和公式,这个总和为 ($\sqrt{n}$ - 1) * $\sqrt{n}$ / 2,进一步化简得到 (n - $\sqrt{n}$) / 2。当 n 趋向于无穷大时,低阶项和常数系数可以忽略不计,因此时间复杂度为 O (n)。
综上,答案选 B。
登录后提交答案
暂无评论,来抢沙发