下面 sum_digit 函数求 1 到 n 中包含数字 d 的个数，其时间复杂度为：
int count_digit(int n, char d) {
int cnt = 0;
std::string s = std::to_string(n);
for (int i = 0; i < s.length(); i++)
if (s[i] == d) cnt++;
return cnt;
}
int sum_digit(int n, char d) {
int sum = 0;
for (int i = 1; i <= n; i++)
sum += count_digit(i, d);
return sum;
}
- A. O(n log n)
- B. O(n)
- C. O(log n)
- D. O(n²)
正确答案：A