题目
第 1 题：设 n是描述问题规模的非负整数，下面程序片段的时间复杂度是 。x=2; while(x A. O(log 2 n)B. O(n)C. O(nlog 2 n)D. O(n 2 )
第 1 题：设 n是描述问题规模的非负整数，下面程序片段的时间复杂度是 。x=2; while(x < n/2)x=2*x ;
A. O(log 2 n)
B. O(n)
C. O(nlog 2 n)
D. O(n 2 )
题目解答
答案
A. O(log 2 n)
解析
步骤 1：确定循环条件
程序片段中的循环条件是 x < n/2。初始时，x=2，每次循环 x 的值翻倍，即 x=2*x。
步骤 2：计算循环次数
设循环执行了 T(n)次。每次循环 x 的值翻倍，因此循环结束后 x 的值为 2^{T(n)+1}。根据循环条件，有 2^{T(n)+1} < n/2。解此不等式，得 T(n)+1 < log _2 (n/2) = log _2 n - 1，即 T(n) < log _2 n - 2。因此，T(n) = O(log _2 n)。
步骤 3：确定时间复杂度
由于循环中执行的语句 x=2*x 的时间复杂度为 O(1)，因此整个程序片段的时间复杂度为 O(T(n)) = O(log _2 n)。
程序片段中的循环条件是 x < n/2。初始时，x=2，每次循环 x 的值翻倍，即 x=2*x。
步骤 2：计算循环次数
设循环执行了 T(n)次。每次循环 x 的值翻倍，因此循环结束后 x 的值为 2^{T(n)+1}。根据循环条件，有 2^{T(n)+1} < n/2。解此不等式，得 T(n)+1 < log _2 (n/2) = log _2 n - 1，即 T(n) < log _2 n - 2。因此，T(n) = O(log _2 n)。
步骤 3：确定时间复杂度
由于循环中执行的语句 x=2*x 的时间复杂度为 O(1)，因此整个程序片段的时间复杂度为 O(T(n)) = O(log _2 n)。