Временная сложность оптимизированной функции анаграммы - PullRequest
Новая
       7

Временная сложность оптимизированной функции анаграммы

0 голосов
/ 04 марта 2020

Это не проблема домашней работы. Я готовлюсь к собеседованию и провёл немало исследований по ссылкам на этот пост . Я разработал решение, основанное на предложении, но я не согласен с предложенной сложностью времени. Я хотел бы знать, правильно ли я / неправильно в моем утверждении.

Ниже приведена функция для выделения группы анаграмм. Он сортировал каждое входное слово и помещал отсортированное входное слово в словарь. Я сам написал код, основываясь на подсказке из публикации geeksforgeeks , в которой предлагается:

Использование сортировки: мы можем отсортировать массив строк так, чтобы все анаграммы собрались вместе. Затем распечатайте все анаграммы путем линейного обхода отсортированного массива. Временная сложность этого решения - O (mnLogn) (мы будем делать O (nLogn) сравнений в сортировке, а сравнение займет O (m) времени). Где n - количество строк, а m - максимальная длина строки.

Я не согласен с упомянутой сложностью времени

Я думаю, что сложность времени для следующего кода равна n (m лог м). Сложность пространства: O (2n) = O (n) для результатов и переменная sorted_dict

n = количество слов, m = количество символов в слове 

def groupAnagrams(strs):
  sorted_dict ={}
  results=[]
  for each in strs:#loop: O(n)
     #time complexity for sort: O(m log m). 
     sorted_str = "".join(sorted(each.lower())) #O(m) 
     if  not sorted_dict.get(sorted_str):  #0(1)
         sorted_dict[sorted_str] = []
     sorted_dict[sorted_str].append(each) #0(1)

  for k,v in sorted_dict.items(): #0(n)
     results.append(v)
  return results

1 Ответ

1 голос
/ 06 марта 2020

Ваш алгоритм имеет временную сложность O (mn log m), в которой преобладает время, необходимое для сортировки каждой из строк в массиве; так что ваш анализ верен. Однако ваш результат отличается от того, который вы цитировали не потому, что цитата неверна, а потому, что ваш алгоритм отличается от того, который был проанализирован в цитате. Обратите внимание, что цитата гласит:

Мы можем отсортировать массив строк так, чтобы все анаграммы собрались вместе.

Ваш алгоритм этого не делает; он вообще не сортирует массив строк, а сортирует символы в каждой строке по отдельности. Вот реализация в Python алгоритма, о котором говорится в этой цитате: 

from itertools import groupby

NO_OF_CHARS = 256

def char_freqs(word):
    count = [0] * NO_OF_CHARS
    for c in word: 
        count[ord(c)] += 1
    return count

def print_anagrams_together(words):
    words = sorted(words, key=char_freqs)
    for _, group in groupby(words, key=char_freqs):
        print(*group, sep=', ')

Сложность по времени можно определить следующим образом:

  • char_freqs принимает O ( m) время из-за итерации по строке длиной m.
  • Сортировка занимает O (mn + n log n) времени, потому что ключевая функция занимает O (m) времени и вызывается для n строк, а затем строки отсортированы за O (n log n) времени. Сравнения в сортировке выполняются в списках длиной NO_OF_CHARS (константа), поэтому сравнения занимают постоянное время.
  • Группировка слов вместе занимает время O (mn), потому что доминирует повторный вызов char_freqs n раз; это может быть улучшено до O (n) путем повторного использования уже вычисленных ключей из сортировки, но в любом случае в этой части преобладает сортировка.

Это дает общую сложность времени O (mn + n). log n), что не совпадает с кавычками, но вы получите O (mn log n), если ключевая функция char_freqs вызывается для каждого сравнения , а не один раз для каждого элемента и кэшируется. Например, если вы выполнили сортировку в Java, используя что-то вроде: 

// assuming that charFreqs returns something comparable
Collections.sort(words, Comparator.comparing(Solution::charFreqs));

Тогда сравнение заняло бы время O (m) вместо времени O (1), и общая сложность времени была бы O (mn log n). Таким образом, цитата не ошибочна, она просто говорит о алгоритме, отличном от того, о котором вы думали, и предполагает его неоптимальную реализацию.

...