2011 数据结构第1题

2011 数据结构 ★★★☆ 复杂度分析选择题

第 1 题

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

x = 2;
while (x < n / 2)
    x = 2 * x;

A. $O(\log n)$

B. $O(n)$

C. $O(n\log_2 n)$

D. $O(n^2)$

[tag_link]

正确答案：A

在程序中，执行频率最高的语句为x = x * 2，设该语句总共执行了 T(n) 次，则2T(n)+1≤n/2，故T(n)=log2(n/2)−1=log2n−2，得T(n)=O(log2n)。