c++ 时间复杂度O(n)

x8diyxa7  于 2023-03-05  发布在  其他
关注(0)|答案(1)|浏览(193)

我正在尝试创建一个识别字谜的程序。下面是提示符:
如果两个字符串的字母可以重新排列以形成彼此,则这两个字符串是变位词。例如,"Eleven plus two"是"Twelve plus one"的变位词。每个字符串包含一个"v"、三个"e"、两个"l"等。编写一个程序来确定这两个字符串是否是变位词。该程序不应区分大小写,并且应忽略任何标点符号或空格。
注:
1.考虑如何将实现分解为函数。
1.注意程序的运行时间,如果每个输入字符串包含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;
}
ylamdve6

ylamdve61#

不,它不是线性的,因为每次调用这些函数-〉quadratic时,都会复制一个行字符串,使用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在这里是多余的。

为了确保它是线性时间,我应该寻找哪些东西?
你可以像评论者说的那样测量它的执行时间,这通常是你试图优化的目标,但一般来说,你是在寻找循环和你调用的所有函数的执行时间。

相关问题