Временная сложность этого кода (из интервью Cracking the Coding «Групповые анаграммы») - PullRequest
Новая
       5

Временная сложность этого кода (из интервью Cracking the Coding «Групповые анаграммы»)

0 голосов
/ 28 декабря 2018

Автор утверждает, что следующий код является O (n * log (n)).Кажется, это подразумевает, что Comparator выполняет работу в постоянном времени, но есть функция, встроенная в функцию сравнения () Comparator.Разве это не увеличивает сложность времени? 

class AnagramComparator implements Comparator<String> {
  public String sortChars(String s) {
    char[] content = s.toCharArray();
    Array.sort(content);
    return new String(content);
  }

  public int compare(String s1, String s2) {
    return sortChars(s1).compareTo(sortChars(s2));
  }
}

Arrays.sort(array, new AnagramComparator());
...