CSP-J 2022 第一轮 第 28 题：程序（三，牛顿迭代求平方根）：时间复杂度是否为O(log n+k)

题目

1  #include <iostream>
2
3  using namespace std;
4
5  int n,k;
6
7  int solve1()
8  {
9      int l = 0, r = n;
10     while(l <= r){
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17
18 double solve2(double x)
19 {
20         if (x == 0) return x;
21         for (int i = 0; i < k; i++)
22             x = (x + n / x) / 2;
23     return x;
24 }
25
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

该算法最准确的时间复杂度分析结果为 $O(\log n+k)$。

选项

• A. 正确
• B. 错误

答案

A

题解

选 A. 正确。

程序依次执行 solve1() 和 solve2()：

• solve1()：\(O(\log n)\)

用二分查找求 \(\lfloor\sqrt n\rfloor\)。每次循环将查找区间缩小约一半，因此循环次数为 \(O(\log n)\)。

• solve2()：\(O(k)\)

当 \(n>0\) 时，传入的 x 至少为 1，for 循环恰好执行 \(k\) 次，每次只做常数次运算，因此为 \(O(k)\)。即使牛顿迭代已经收敛，代码也不会提前退出。

两部分是顺序执行，时间复杂度相加，得到 \[ \boxed{O(\log n+k)}. \]

补充：\(n=0\) 时程序耗时为 \(O(1)\)。若要兼顾零值并严格书写，可以写成 \(O(1+\log(n+1)+k)\)，不影响本题选 A。