performance - 有没有办法降低 O(n^2) 的时间复杂度？

Question

我做了一个程序(hw)，它计算所有单词的频率。 我所有的算法都需要 O(n) 或 O(n log n)，但是我的单词计数器需要 O(n^2)

算法如下所示:

for (int i = 0; i < no of elements; i++)
            for (int j = 0; j < no of elements; j++)
                if (the ith word == the jth word)
                {
                    increase that word counter by 1;
                    break;
                }

我使用这种方式的原因是因为单词列表是未排序的。所以我的问题是，使用插入排序或可以按字母顺序对单词列表进行排序的排序是个好主意吗？字符串数组的这种排序方式如何？ 单词列表是一个字符串数组，eg:

string words[no of elements]

感谢您的宝贵时间。

Answer 1

为您的单词创建哈希表，然后您的单词计数将为 O(n)，因为哈希表查找将为 O(1)。