c++ - 降低 o(n^3) c++ 代码的复杂性

Question

我想降低以下算法的复杂性。基本上，它以一个词作为输入并计算其中唯一字母的数量(该词的“熵”)。我当前的解决方案采用 3 个嵌入式 for 循环，复杂度为 o(n^3)。由于这段代码是一个更大项目的一部分(我们为名为 boggle 的游戏构建了一个求解器)，我希望降低算法的复杂性以减少其执行时间。提前致谢!

int wordEntropy(string word)
{

int length = word.length();
int uniquewords = length;
string compare = word;
char save[17];
int cond=0;

for (int ii=0; ii < length; ii++)
{

    for (int jj=ii+1; jj < length; jj++)
    {
        for (int kk=0; kk<= ii; kk++)
        {
            if (save[kk] == word[ii]) {cond++;}
        }
        if (word[ii] == word[jj])
        {
            if (cond>0) {break;}
            uniquewords--;
        }
    }

    save[ii] = word[ii];
    cond = 0;

}
return uniquewords;
}

Answer 1

一个廉价的解决方案是将字符放在 unordered_set 中，这是一个哈希集(分摊 O(1) 插入和查找):

#include <unordered_set>

int wordEntropy(const std::string &word) {
    std::unordered_set<char> uniquechars(word.begin(), word.end());
    return uniquechars.size();
}

这会产生 O(n) 的复杂度，这已经很好了。