阅读程序第3题

阅读下面的程序，完成第29—35题。

void print(std::string in)
{
    int q[2000] = {10, 0};
    int out[2000] = {0};
    int size = 1;
    for (char c : in)
    {
        int r = 0;
        for (int i = 0; i < size; ++i) {
            r = r * 10 + q[i];
            q[i] = r / 2;
            r = r % 2;
        }
        while (r > 0) {
            r = r * 10;
            q[size] = r / 2;
            size++;
            r = r % 2;
        }

        int d = c - '0';
        int i = size - 1;
        while (true) {
            out[i] += q[i] * d;
            int carry = out[i] / 10;
            out[i] %= 10;
            if (i > 0) {
                --i;
                out[i] += carry;
            }
            else {
                break;
            }
        }
    }

    while (size > 1 && out[size-1] == 0) {
        size--;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << out[i];
    }
}

若输入的数据长度为 $n$，该程序的时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(\sqrt{n})$
• $\Theta(n)$
• $\Theta(n \log n)$
• $\Theta(n^2)$