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

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

复杂度分析

A. (O(n)) B. (O(\sqrt{n})) C. (O(n\log_2 n)) D. (O(\log_2 n))

[tag_link]

正确答案：B

假设第 k 次循环终止，则第 k 次执行时，(x+1)2>n，x 的初始值为 0，第 k 次判断时，x=k-1，即k2>n，k>n1/2,，因此该程序段的时间复杂度为O(n1/2)。