算法

算法甜品

问: 设n是描述问题规模的非负整数,下面程序片段的时间复杂度是

x = 2 ;

while (x<n/2)

x = 2 * x ;

解:设其执行时间为T(n) , 则有2^T(n) < n/2 , 即T(n) < log2 n/2 = O(log2 n). (因为x = 2*x 这里要注意)

发表评论

电子邮件地址不会被公开。 必填项已用*标注