Каковы сложности времени выполнения Java Comparator?

Question

У меня есть пользовательский объект, скажем, Person.java с полями String name и int age.Допустим, у меня есть 100 различных экземпляров объекта Person, которые я хочу отсортировать с помощью пользовательского компаратора, так что самые старые люди пойдут раньше, чем самые молодые.Написание самого компаратора легко - просто реализуйте метод CompareTo, и я поместу объекты в List (или Queue будет лучше?).Тем не менее, что будет время выполнения этого метода сравнения?Это быстрее, чтобы выполнить какой-то собственный метод сортировки сам?

Answer 1

Какой будет среда выполнения этого метода сравнения?

Это зависит от того, как вы его реализуете (!). Однако, если вы просто сравниваете значения полей age и / или name в соответствующих объектах, это должно быть O(1).

Сложность алгоритма сортировки обычно указывается с точки зрения количества сравнений, которые он выполняет. Таким образом, если выбранный алгоритм сортировки равен O(NlogN), а ваш Comparator равен O(1), мы можем предсказать ¹ , что общая сложность будет O(NlogN x 1) или O(NlogN).

Быстрее ли выполнить какой-либо собственный метод сортировки сам?

Нет. Это, конечно, не улучшит сложность, если вы реализуете пользовательскую сортировку. (Вы не можете сделать лучше, чем O(NlogN) для однопоточной сортировки общего назначения.)

• Если вы вручную «встроите» код сравнения в свою пользовательскую сортировку, вы все равно будете выполнять те же операции для сравнения полей и делать то же количество раз.

• В более общем смысле алгоритмы, используемые встроенным sort(...) в Java 8 и более поздних версиях, представляют собой современные алгоритмы. Вы вряд ли улучшите их без значительных затрат (на разработку и / или ремонтопригодность).

---

Этот вопрос пахнет " преждевременная оптимизация ". Пожалуйста, прочитайте, что это значит и почему это (обычно) плохо.

---

^{1 - Я не утверждаю, что это правильное доказательство. Хотя я думаю, что правильное доказательство даст и этот ответ.}

Answer 2

Полагаю, вы используете JDK8 или аналогичный.

В большинстве случаев вам просто нужен следующий код для выполнения описанной вами задачи с очень хорошей производительностью:

List<Person> list = new ArrayList<>();
list.add(p1);
list.add(p2);
// adding all elements
...
list.sort(comparator);

В качестве альтернативы, если вы реализуете Comparable интерфейс, вы можете использовать Collections.sort() метод. Для получения дополнительной информации см. List.sort () и Collections.sort () .

Сложность времени выполнения

Строка list.sort(comparator); имеет сложность времени выполнения

O(n) x O(log(n)) x C

Мы должны рассмотреть 2 части:

1. O(n) x O(log(n)): относится к алгоритму сортировки, как описано в документации List.sort () , в худшем случае мы можем ожидать n*log(n), поэтому я использую большой O, но если список частично отсортирован, время выполнения близко к n.
2. C: относится ко времени выполнения реализации compareTo(), как вы уже упоминали, вы просто сравниваете их возраст, это довольно просто, не должно вызывать беспокойства. Поэтому ожидается, что время выполнения этой реализации будет постоянным, или O(1). (это может быть то, что вы просите)

Если вторая точка истинна, общая сложность времени выполнения должна быть выражена как:

O(n) x O(log(n))