减少一段 O(n^3) 的 C++ 代码的复杂性

Question

我希望能简化下面这个算法的复杂度。基本上，它以一个单词作为输入，并计算其中唯一字母的数量（即单词的“熵”）。我的当前解决方案使用了三个嵌套的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;
}

- Patrick Fuentes

---

保持简单？循环遍历单词，记录在位集中看到的字母。最后，对位集求和。时间复杂度为O(n+m)，其中n是单词长度，m是字母表大小（即26）。 - Colonel Panic

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)的复杂度，这已经是最好的情况了。

- nneonneo

---

平均情况下，这是O(N)，但最坏情况可能达到O(N^2)。不确定需要什么才能使这种情况最坏。 - NathanOliver

@NathanOliver 如果要达到最坏情况，你需要一个糟糕的实现unordered_set或者一个糟糕的hash<char>实现。这是导致哈希集性能下降的原因。 - Xirema

@Xirema 那么它就与碰撞有关了吗？ - NathanOliver

@NathanOliver 是的。 - Xirema

Answer 2

在原地进行计算，不需要额外的（耗时的）内存分配：

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

- Pete Becker

---

值得注意的是，对于长字符串，这将是O(n log n)的时间复杂度。（对于典型的Boggle单词，这种差异可能并不重要）。 - nneonneo

对于典型的Boggle单词，与使用某种形式的set相比，区别很重要：所有set的内存开销和运行时复杂度都远远超过排序短单词所需的“额外”工作量。性能评估远不止渐近复杂度这一方面。 - Pete Becker

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; } );
}

- Markus Mayr

---

你可能需要将其编写为 for (unsigned char c : word)，因为许多 C++ 实现将 char 的范围视为 [-128, 127]。 - Xirema

如果你遇到了16位字符，你还需要将其中的256替换为std::numeric::limits<std::string::value_type>::max()。 - NathanOliver

是的，以上所有内容都是真实的。此外，如果一个字符在单词中出现超过255次，则原始算法会失败，我提供了一个修复此问题的替代版本。 - Markus Mayr

@Xirema 实际上，两者都是正确的。其中 M 是可表示字符数/按合同可能存在于单词中的字符数，N 是单词中字符数，即单词的大小。时间复杂度为 O(M+N)。 - Markus Mayr

个人而言，我会选择 std::sort + std::unique，但如果涉及到性能，一定要将其与其他解决方案进行比较。对于短单词长度，我预计 std::sort + std::unique 方法将优于这种方法。 - Markus Mayr

Answer 4

如果字符串很短，那么你应该更担心内存分配而不是大O表示法。无论如何，这里有一个更快的解决方案。

既然你提到这是为了Boggle游戏，而这个函数的输入是一个名为"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 );
}

- KevinZ