题目
.设 n 是描述问题规模的非负整数,下面程序片段的时间复杂 度是( )。x = 2:while ( x<n/2 )x= 2X x;A. O( log 2n) B. O( n) C. O( nlog 2n) D. O( n2)
.设 n 是描述问题规模的非负整数,下面程序片段的时间复杂 度是( )。
x = 2:
while ( x<n/2 )
x= 2X x;
A. O( log 2n)B. O( n)
C. O( nlog 2n)
D. O( n2)
题目解答
答案
[答案] A [解析] 其中,以基本的原操作重复执行的次数作为算法的时间 度量。题目中的基本运算是语句 x = 2X x,设其执行时间为T (n),
解析
步骤 1：确定循环条件
程序片段中的循环条件是 `x < n/2`。初始时，`x = 2`，每次循环 `x` 的值翻倍，即 `x = 2 * x`。因此，循环会一直执行，直到 `x` 不再小于 `n/2`。
步骤 2：计算循环次数
设循环执行了 `k` 次，那么 `x` 的值为 `2^k`。循环结束时，`2^k` 应该大于或等于 `n/2`。因此，我们有 `2^k >= n/2`。取对数，得到 `k >= log_2(n/2)`。由于 `log_2(n/2) = log_2(n) - 1`，所以 `k >= log_2(n) - 1`。因此，循环次数 `k` 大约为 `log_2(n)`。
步骤 3：确定时间复杂度
由于循环次数 `k` 大约为 `log_2(n)`，因此程序片段的时间复杂度为 `O(log_2(n))`。
程序片段中的循环条件是 `x < n/2`。初始时，`x = 2`，每次循环 `x` 的值翻倍，即 `x = 2 * x`。因此，循环会一直执行，直到 `x` 不再小于 `n/2`。
步骤 2：计算循环次数
设循环执行了 `k` 次，那么 `x` 的值为 `2^k`。循环结束时，`2^k` 应该大于或等于 `n/2`。因此，我们有 `2^k >= n/2`。取对数，得到 `k >= log_2(n/2)`。由于 `log_2(n/2) = log_2(n) - 1`，所以 `k >= log_2(n) - 1`。因此，循环次数 `k` 大约为 `log_2(n)`。
步骤 3：确定时间复杂度
由于循环次数 `k` 大约为 `log_2(n)`，因此程序片段的时间复杂度为 `O(log_2(n))`。