Question

数据结构（c语言版）

1.下面程序段的时间复杂度是__O(n^(1/2))____
i=s=0
While(s<n)
{
i++; /* i=i+1 */
s+=i; /* s=s+i */
}
2.下面程序段的时间复杂度是___O（log3 N）（注：对N取3的对数）
i=1;
While (i<=n)
i=i*3;
可否详细解释下是怎么做出来的，谢谢啊

Answer 1

1. Si = i*(i+1)/2 = (i^2 + i)/2 < n (经过i次运算)
根据复杂度理论，低阶变量和常量系数可以忽略，可以得出 i^2 < n
所以要经过i < n^(1/2) 次运算， 所以其时间复杂度为O(n^(1/2))

2. 同理 ik = 3^k <n (经过k次运算), k<log3N
所以其时间复杂度为O（log3 N）