降低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)的复杂性,这与它得到的一样好.

Answer 2

在没有任何额外(和耗时)内存分配的情况下进行计算:

std::sort(word.begin(), word.end());
auto last = std::unique(word.begin(), word.end());
return last - word.begin();

Answer 3

如果这真的是关于性能,取决于有效字符的范围,这样的事情可能会更快:

std::size_t wordEntropy( const std::string & word )
{
    unsigned char seen[256] = { 0 };
    for( unsigned char c : word )
    {
        ++seen[ c ];
    }
    return std::count_if( & seen[0], & seen[ 0 ] + 256,
                          []( unsigned char c ) { return c != 0; } );
}

但显然,这有点难以维护.该解决方案保证了O(n)的复杂性,并且它不会进行任何动态内存分配.

如果字符出现次数超过255次,则没有问题的替代版本:

std::size_t wordEntropy( const std::string & word )
{
    bool seen[256] = { false };
    for( unsigned char c : word )
    {
        seen[ c ] = true;
    }
    return std::count_if( & seen[0], & seen[ 0 ] + 256,
                          []( bool t ) { return t; } );
}