CSP-S 2022 第一轮 第28题：该算法的时间复杂度为 0(logk n)。（)

题目

1  #include <iostream>
2  #include <algorithm>
3
4  using namespace std;
5
6  const int MAXL = 1000;
7
8  int n, k, ans[MAXL];
9
10 int main(void)
11 {
12     cin >> n >> k;
13     if (!n) cout << 0 << endl;
14     else
15     {
16         int m = 0;
17         while (n)
18         {
19             ans[m++] = (n % (-k) + k) % k;
20             n = (ans[m - 1] - n) / k;
21         }
22         for (int i = m - 1; i >= 0; i--)
23             cout << char(ans[i] >= 10 ?
24                          ans[i] + 'A' - 10 :
25                          ans[i] + '0');
26         cout << endl;
27     }
28     return 0;
29 }

假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：

该算法的时间复杂度为$O(\log_k n)$。

选项

• T. 正确
• F. 错误

答案

T

题解

选 T，正确。

第 19 行得到的余数 ans[m - 1] 在 \(0\) 到 \(k-1\) 之间，第 20 行更新： \[ n=\frac{\text{ans}[m-1]-n}{k} \] 因此，虽然 \(n\) 的正负可能交替变化，但它的绝对值大致每次缩小为原来的 \(1/k\)，经过约 \(\log_k |n|\) 次循环就会变为 0。

• while 循环每次执行常数次运算，总时间为 \(O(\log_k |n|)\)。
• for 循环输出所有得到的数位，次数与 while 相同。

所以按题目的通常表述，时间复杂度为 \(O(\log_k n)\)，判断正确。

严格考虑负数和 \(n=0\) 时，可以统一写成 \(O(1+\log_k(|n|+1))\)。