第2题

#include<iostream>
int main()
{
    int q[2000] = {10};
    int s[2000] = {0};
    int size = 1;
    char c;
    while (std::cin >> c) {
        int d = c - '0';
        int r = 0;
        for (int i = 0; i < size; ++i) {
            r = r * 10 + q[i];
            q[i] = r / 8;
            r = r % 8;
        }
        while (r > 0) {
            r = r * 10;
            q[size] = r / 8;
            size++;
            r = r % 8;
        }
        for (int i = 0; i < size; ++i)
            s[i] += q[i] * d;
        for (int i = size; i > 0; --i) {
            s[i-1] += s[i] / 10;
            s[i] %= 10;
        }
    }
    while (size > 0 and s[size-1] == 0)
        size --;
    for (int i = 0; i < size; ++i)
        std::cout << s[i];
    std::cout << "\n";
}

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

{{ select(1) }}

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