11 Алгоритмы и их сложность Flashcards
Что такое сортировка?
Сортировка пузырьком:
Алгоритм просматривает массив и сравнивает каждую пару соседних элементов. Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами. O(n^2)
———————————————————————————-
Сортировка вставками:
Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.
Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.
Сортировка выбором:
Запоминаем значение и индекс 0 элемента и во втором цикле ищем минимальное значение в остальном списке(запоминаем индекс и значение) - потом меняем их местами. O(n^2)
———————————————————————————-
Сортировка слиянием:
Сортировка слиянием эффективнее, чем примеры алгоритмов сортировки, представленные выше, благодаря использованию рекурсии и подходу «разделяй и властвуй».
Массив делится на два подмассива, а затем происходит:
1) Сортировка левой половины массива (рекурсивно)
2) Сортировка правой половины массива (рекурсивно)
3) Слияние
O(nlogn)
———————————————————————————-
Расскажите об интерфейсах Comparable и Comparator?
Comparable и Comparator являются интерфейсами и могут использоваться для сортировки элементов коллекции.
Интерфейс Comparable содержит один единственный метод int compareTo(T item), который сравнивает текущий объект с объектом, переданным в качестве параметра.
Если этот метод возвращает отрицательное число, то текущий объект будет располагаться перед тем, который передается через параметр. Если метод вернет положительное число, то, наоборот, после второго объекта. Если метод возвращает ноль, значит, оба объекта равны.
Для того чтобы объекты можно было сравнить и сортировать, они должны реализовать параметризованный интерфейс Comparable.
Comparable:
- Comparable обеспечивает единую последовательность сортировки. мы можем отсортировать коллекцию на основе одного элемента, (идентификатор, имя и цена).
- Comparable влияет на исходный класс, т.е. модифицируется фактический класс.
- Comparable предоставляет метод compareTo() для сортировки элементов.
- Comparable присутствует в пакете java.lang.
- Мы можем отсортировать элементы списка типа Comparable методом Collections.sort(List).
Comparator:
Comparator предоставляет метод compare() он тоже возвращает числовое значение - если оно отрицательное, то объект A предшествует объекту B, иначе - наоборот. А если метод возвращает ноль, то объекты равны.
Для применения интерфейса нам вначале надо создать класс компаратора, который реализует этот интерфейс.
- Comparator предоставляет несколько последовательностей сортировки. мы можем отсортировать коллекцию по нескольким элементам, ( идентификатор, имя, цена и т. д.)
- Comparator не влияет на исходный класс, т.е. фактический класс не изменяется.
- Comparator предоставляет метод compare() для сортировки элементов.
- Comparator присутствует в пакете java.util.
- Мы можем отсортировать элементы списка типа Comparator методом Collections.sort(List, Comparator).
Начиная с JDK 8 в механизм работы компараторов были внесены некоторые дополнения. В частности, теперь мы можем применять сразу несколько компараторов по принципу приоритета.
Интерфейс компаратора определяет специальный метод по умолчанию thenComparing, который позволяет использовать цепочки компараторов для сортировки набора
Comparator pcomp = new PersonNameComparator().thenComparing(new PersonAgeComparator());
TreeSet people = new TreeSet(pcomp);
интерфейс Comparator позволяет сравнивать между собой два объекта.
Comparator comparator = (p1, p2) -> p1.firstName.compareTo(p2.firstName);
Person p1 = new Person(“John”, “Doe”);
Person p2 = new Person(“Alice”, “Wonderland”);
comparator.compare(p1, p2); // > 0
comparator.reversed().compare(p1, p2); // < 0
Что такое бинарное дерево?
Двоичное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух детей. Как правило, первый называется родительским узлом, а
дети называются левым и правым наследниками.
Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.
Двоичное дерево поиска (binary search tree, BST) — это двоичное дерево, для которого выполняются следующие условия:
● Оба поддерева — левое и правое — являются двоичными деревьями поиска.
● У всех узлов левого поддерева произвольного узла X значения ключей меньше, нежели значение ключа самого узла X.
● У всех узлов правого поддерева произвольного узла X значения ключей больше либо равны, нежели значение ключа самого узла X.
Как можно отсортировать с помощью обхода бинарного дерева?
В порядке in-order.
При условии, что у всех узлов дерева значение левого потомка меньше значения родителя, а правого больше - рекурсивно обойти левое поддерево, вывести значение узла, потом обойти правое поддерево.
TreeSet и TreeMap основаны на BST(binary search tree)
Два подхода:
Поиск в глубину (Depth-first search DFS)
Поиск в ширину (Breadth-first search BFS)
DFS: pre-order: Посетить узел Обойти левое поддерево Обойти правое поддерево 8 3 1 6 4 7 10 14 13 in-order: Обойти левое поддерево Посетить узел Обойти правое поддерево 1 3 4 6 7 8 10 13 14 post-order: Обойти левое поддерево Обойти правое поддерево Посетить узел 1 4 7 6 3 13 14 10 8
Опишите быструю сортировку?
Быстрая сортировка происходит рекурсивно. Сначала мы сортируем массив относительно значения опорного элемента, те что меньше перемещаются в левую часть, те что больше в правую. Затем рекурсивно сортируем левый подмассив и правый. Сложность O(nlogn)
Статический утилитный метод
java.util.Arrays.sort(массив);
массив - ссылка на массив примитивов или массив объектов, имплементирующих интерфейс Comparable
Количество уровней разбиения порядка log(n), на каждом из которых
порядка n операций сравнения. Таким образом общая сложность - nlog(n).
алгоритмы и их сложность?
Алгоритм - это последовательность действий приводящих к решению любой поставленной задачи
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. Асимптотическая сложность - это сложность при стремлении размера входных данных к бесконечности. Сложность описывается обычно с помощью буквы O. Примеры: O(1) – константная сложность O(n) - линейная сложность O(log n) - логарифмическая сложность O(n*log(n)) - квазилинейная сложность O(n2) - квадратичная сложность O(2^n) - экспоненциальная сложность.
