我的代码在线性时间内运行吗？ (O(n))

Question

我正在尝试创建一个识别字谜的程序。这是提示：

如果字母可以重新排列形成彼此，则两个字符串是变位词。例如， “十一加二”是“十二加一”的变位词。每个字符串包含一个‘v’，三个‘e’， 两个“l”等 编写一个程序来确定两个字符串是否是变位词。程序不应该是大小写 敏感，应忽略任何标点符号或空格。

备注：

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."
    );
    delete[] letterCount1;
    delete[] letterCount2;
}

Answer 1

不，它不是线性的，因为每次调用这些函数时都会复制线串 -> 二次函数。使用

const std::string& line

避免复制。那我觉得是线性的

一些想法：

• 直接将字符传递给

  letterArray

  ，而不是传递数组+索引。函数对调用上下文的了解越少，它就会变得越简单和通用。
• 不要使用原始

  new

  ，只需使用

  std::vector

  ，如果在编译时知道大小并且您关心分配，请使用

  std::array

  。

• isAnagram

  实际上是在测试两个数组的相等性，

  std::vector

  会用

  ==

  为您做的事情。

  std::equal

  可用于您拥有的原始数组。

• line1.length() || i < line2.length()

  你想要

  &&

  在那里，否则你会越界。是的，您必须在循环后完成对较长字符串的处理。但是为什么首先将这两个调用放在一个循环中呢？它们彼此独立。我会建议

  processLine

  函数构造字符计数数组并返回它。

• isAnagram(letterCount1, letterCount2) == true

  确定你可以明确，但因为你已经为函数选择了一个好名字，所以

  ==true

  在这里是多余的。

我应该寻找哪些东西来确保它是线性时间？

好吧，你可以像评论者说的那样测量它的执行时间。无论如何，这通常是您要尝试优化的目标。但一般来说，您正在寻找循环和您调用的所有函数的执行时间。