判断我的变位词识别代码是否为线性时间复杂度（O(n)）

需求与问题 #

若两个字符串的字母可重新排列形成彼此，则互为变位词，例如“Eleven plus two”与“Twelve plus one”。程序需不区分大小写，忽略标点与空格。
注意事项：

1. 需拆分实现为函数；
2. 若输入字符串含n个字符，高效实现应为线性时间复杂度（即Θ(n)）。

我不确定自己写的代码是否为线性时间复杂度，请问需关注哪些要点来确认？

代码实现 #

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

const char SPACE = ' ';
const char PERIOD = '.';
const char COMMA = ',';
const char A = 'A';
const char Z = 'Z';
const char a = 'a';
const char z = 'z';

void letterArray(string line, int i, int*& letterCount) {
    if(line[i] >= a && line[i] <= z) {
        letterCount[line[i] - a]++;
    } else if (line[i] >= A && line[i] <= Z) {
        letterCount[line[i] - A]++;
    }
}

bool isAnagram(int*& arr1, int*& arr2) {
    bool anagram = true;
    for (int i = 0; i < 26; i++) {
        if(arr1[i] != arr2[i]) {
            anagram = false;
        }
    }
    return anagram;
}

int main() {
    string line1;
    string line2;
    int * letterCount1 = new int[26];
    int * letterCount2 = new int[26];
    getline(cin, line1);
    getline(cin, line2);
    for(int i = 0; i < line1.length() || i < line2.length(); i++) {
        letterArray(line1, i, letterCount1);
        letterArray(line2, i, letterCount2);
    }
    if(isAnagram(letterCount1, letterCount2) == true) {
        cout<<"These two strings are anagrams."<<endl;
    } else {
        cout<<"These two strings are not anagrams."<<endl;
    }
    delete[] letterCount1;
    delete[] letterCount2;
}

时间复杂度确认要点 #

要确认代码是否为线性时间复杂度（Θ(n)），核心看以下几点：

• 输入遍历的次数与方式
  线性复杂度要求程序对每个输入字符仅做常数次操作，不能出现嵌套遍历（比如外层遍历每个字符，内层再遍历整个字符串）。你的代码里，对两个字符串的遍历是单次循环（虽然逻辑有问题，但次数是max(len(line1), len(line2))），每个字符的处理都是O(1)的判断和计数，这部分符合线性要求。

  注意：你的代码当前有越界bug——当i超过其中一个字符串的长度时，访问line[i]会触发未定义行为，建议改成分别遍历两个字符串，避免越界。

• 固定次数的循环不影响复杂度
  像isAnagram里遍历26个字母的循环，次数是固定常数（26），属于O(1)的开销，不会把整体复杂度拉到非线性，因为不管输入字符串多长，这部分的操作次数都不变。

• 避免隐性的非线性操作
  比如不要用排序（排序的时间复杂度是O(n logn)）、不要用会随输入规模增长的嵌套逻辑。你的代码用数组计数的方式，每个字符的计数操作都是O(1)，没有这类非线性操作。

• 操作的常数性
  每个字符的处理逻辑（判断是否为大小写字母、更新计数）都是固定时间的操作，没有依赖输入规模的耗时步骤，比如字符串拼接、复杂计算等，这也是线性复杂度的必要条件。

你的代码的复杂度结论 #

你的代码整体时间复杂度是Θ(n)，其中n是两个输入字符串的总长度（或较长字符串的长度），符合需求。但需要先修复字符串越界的bug，才能保证程序正确运行。

内容的提问来源于stack exchange，提问作者patriphied