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