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

Question

我想降低以下算法的复杂性。基本上，它以一个词作为输入并计算其中唯一字母的数量（该词的 "entropy"）。我当前的解决方案采用 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; } );
}

Answer 4

如果字符串很短，那么您应该比 big-O 更担心内存分配。无论哪种方式，这里都有一个更快的解决方案。

既然你提到这是一个boggle game，并且这个函数的输入是一个名为"word"的字符串，我假设你已经验证了"word"中的所有字符是 ascii 字母字符。如果是这样，这可能是最快的大小写不变熵计数：

int word_entropy ( std::string const& word )
{
    uint32_t bit_map = 0;
    for ( char const ch : word )
        bit_map |= static_cast <uint32_t> ( 1 ) << ( ch & 31 );
    return __builtin_popcount ( bit_map );
}

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

Reducing the complexity of an o(n^3) c++ code

c++

algorithm

performance

for-loop

code-complexity