Core-2: Comparator, Сложность Алгоритмов

Question 1

Что такое Time Complexity?

Answer 1

Количество операций, выполняемых для достижения результат

Question 2

Что такое O(1) / O(n) / O(log n) / O(n log n)

Answer 2

• O(1): константное время, одна операция
• O(n): сложность возрастает пропорционально кол-ву элементов
• O(log n): n=8 => 2^(log n)=8 => log n = 3;
• O(n log n): n=4; n log n = 4log4= 42=8;

Question 3

В чем контракт между equals() & compareTo()?

Answer 3

if a.equals(b) == true
=>
a.compareTo(b) == 0

Question 4

Comparator vs. Comparable.

Answer 4

Интерфейс Comparable является хорошим выбором, когда он используется для определения порядка по умолчанию или, другими словами, если это основной способ сравнения объектов.
Затем мы должны спросить себя, зачем использовать Comparator, если у нас уже есть Comparable?
Есть несколько причин, почему:
Иногда мы не можем изменить исходный код класса, чьи объекты мы хотим отсортировать, что делает невозможным использование Comparable
Использование компараторов позволяет нам избежать добавления дополнительного кода в классы нашего домена
Мы можем определить несколько разных стратегий сравнения, что невозможно при использовании Comparable

Question 5

Какие виды “natural order” существуют?

Answer 5

• arithmetic order: 1, 2, 3, …;
  
  • lexicographic order (alphabetical or dictionary): “a”, “an”, “bee”, …;
  • chronological: 2020-12-31, 2021-01-01, 2021-01-02, ….

Question 6

Как создать Comparator с помощью лямбд?

Answer 6

Comparator<Laptop> byNumberOfCores =
(l1,l2)->Integer.compare(l1.getCoresNum(), l2.getCoresNum());
=>
 Comparator.comparingInt(Laptop::getCoresNum);

Question 7

Основные методы Компаратора

Answer 7

• int compare(T o1, T o2);
• default Comparator<T> reversed() :
  ~~~
  laptops.sort(Comparator.comparing(
  SomeClass::someMethod, Comparator.reverseOrder())
  ~~~

- default Comparator<T> thenComparing(Function<T,U> keyExtr)
 SomeClass::someMethod, Comparator.reverseOrder())
		.thenComparingDouble(Laptop::getDisplaySize));

- public static <T, U> Comparator<T> comparing(
            Function<? super T, ? extends U> keyExtractor,
            Comparator<? super U> keyComparator) 

- comparingInt(ToIntFunction<? super T> keyExtractor) ..Long, ..Double
- thenComparingInt(ToIntFunction<? super T> keyExtractor) ..Long, ..Double

• public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) / nullsLast</T></T>