下面的 sum_digit 函数试图求出从 1 到 n（包含 1 和 n）的数中，包含数字 d 的个数。该函数的时间复杂度为（ ）。

#include <string>
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;
}

{{ select(1) }}

• $O(n \log n)$
• $O(n)$
• $O(\log n)$
• $O(n^2)$