CSP-J 2021 第一轮 第 25 题：程序（二）：decode函数时间复杂度

题目

#include <iostream>
#include <string>
using namespace std;

char base[64];
char table[256];

void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';

    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}

string decode(string str)
{
    string ret;
    int i;
    for (i = 0; i < str.size(); i += 4) {
        ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            ret += table[str[i + 2]] << 6 | table[str[i + 3]];
    }
    return ret;
}

int main()
{
    init();
    cout << int(table[0]) << endl;

    string str;
    cin >> str;
    cout << decode(str) << endl;
    return 0;
}

设输入字符串长度为 $n$，decode 函数的时间复杂度为（ ）

选项

• A. $O(\sqrt{n})$
• B. $O(n)$
• C. $O(n \log n)$
• D. $O(n^2)$

答案

B

题解

答案是 B. \(O(n)\)。

看 decode 中的循环：

``cpp for (i = 0; i < str.size(); i += 4) ``

每次 i 增加 4，所以循环执行约 \(\frac{n}{4}\) 次。

每次循环中，数组访问、位运算和条件判断都是常数时间，最多向 ret 追加 3 个字符。追加单个字符按均摊 \(O(1)\) 计算，因此总时间为：

\[ O\left(\frac{n}{4}\right)=O(n) \]

注意：每次处理 4 个字符，只是减少了常数倍的循环次数，不改变复杂度的阶。