Есть ли способ сократить мою временную сложность O (n^2)?

Question

Я сделал программу (hw), которая подсчитывает частоту всех слов. Все мои алгоритмы занимает O (п) или O (N журнал 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; 
       } 

причина, почему я использовать таким образом, потому что список слов несортирован. Поэтому мой вопрос: было бы неплохо использовать сортировку вставки или сортировку, которая может сортировать список слов в альфебетическом порядке? И как выглядит такой вид для строкового массива? Список слов является массив строк, например:

string words[no of elements] 

Спасибо за ваше время.

Answer 1

Да, вы можете сортировать свои элементы в O (nlogn) раз, используя любой хороший алгоритм сортировки, такой как quicksort. Затем просто проверьте, повторяются ли повторы по последовательным элементам.

EDIT: на большинстве языков (например, C++) строки можно сравнивать с помощью обычных операторов сравнения. и, следовательно, отсортированы как любой массив. Более того, для этого обычно есть встроенные функции.

Answer 2

Если вы хотите сделать другую структуру данных, воспользуйтесь, пожалуйста, map.

Просто введите map<string, int> слова, чтобы посчитать и обновить его, когда вы перебираете элементы.

(Опять же O (NlogN) во временной сложности)

Answer 3

Make хэш-таблицу для ваших слов, а затем ваше количество слов будет O (п), потому что еси таблица смотреть будет O (1).