请问下面语句段执行的时间复杂度如何计算，求详细的求解步奏
题1
i=1;
while(i<=n)
{
i* = 3;
}
题2
int i=1;
int k= 0;
do
{
k = k+ 10* i;
++i;
}while(i!=n);
第1题的答案应该是O(log(n))。如果循环体内的语句是i+=3，时间复杂度是O(n)。但如果循环体内的语句是i*=3，那么循环体被执行[log3(n)]+1次，所以时间复杂度是O(log(n))级别
第2题的答案是O(n)，因为循环体被执行n-1次
第2题的答案是O(n)，因为循环体被执行n-1次
温馨提示：内容为网友见解，仅供参考
第1个回答 2013-08-16
两个都是O(n)。
循环内的语句看做O(1)，第一个循环内的语句大概执行n/3次，T(n) = n/3 * O(1) = O(n)；第二个循环内的语句执行n-1次（假设n>=2），T(n) = (n-1) * O(1) = O(n)。
循环内的语句看做O(1)，第一个循环内的语句大概执行n/3次，T(n) = n/3 * O(1) = O(n)；第二个循环内的语句执行n-1次（假设n>=2），T(n) = (n-1) * O(1) = O(n)。
相似回答
