НАВИГАЦИЯ

• ALL
  • ALGORITHMS
  • ALGORITHMS COMPLEXITIES
  • SORTING ALGORITHMS
  • SEARCHING ALGORITHMS

Виды сложностей и как ее рассчитывать:

• Time Complexity (Сколько требуется времени на выполнение алгоритма);
• Space Complexity (Сколько требуется памяти для выполнении алгоритма);

Сложность по времени (Time Complexity) выражается аннотацией Большая O (Big O notation). Big O выражает время исполнения алгоритма с точки зрения как изменяется время с изменением входного массива (входной массив обозначается как n).
Подвиды сложности по времени:

• O(1) (Константный) - вычислительная сложность не зависит от входных данных.

• O(n) - Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива.

• O(log n) - (Логарифмический) Порядок роста O(log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (Прим. пер.: в анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность.
  К этой сложности относятся как правило алгоритмы типа "Разделяй и властвуй" ("Divide and Conquer").

• O(n*log n) - (Линеарифметический). Примеры: сортировка слиянием и быстрая сортировка.

• O(n2) - (Квадратичный). Время работы алгоритма с порядком роста O(n 2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. Например, если массив из тысячи элементов потребует. Пример: Пузырьковая сортировка.

• O(2ⁿ) - (Экспоненциальная сложность). Как правило используется в ситуациях когда не известно наилучшее решение и приходится перебирать различные способы.
  Пример этой сложности: Перебор методом Brute-Force.

• Divide - разделение проблемы на подпроблемы такого же типа.
  
• Рекурсивное решение подпроблем.
  
• Объединение подответов полученных из подпроблем.
  

• https://stackoverflow.com/questions/7414667/identify-duplicates-in-a-list

  Один из интересных способов - использовать Set. Пример программы:

   Integer[] dateToTest = {1, 2, 2, 4, 4, 5, 6};
   final Set<Integer> setToReturn = new HashSet<>();
   final Set<Integer> set1 = new HashSet<>();
   for (Integer item : dateToTest) {
   boolean added = set1.add(item);
   if (!added) {
   setToReturn.add(item);
   }
   }
   System.out.println(setToReturn);
  

• https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)
• https://medium.com/nuances-of-programming/%D0%B2%D1%81%D0%B5-%D1%87%D1%82%D0%BE-%D0%BD%D1%83%D0%B6%D0%BD%D0%BE-%D0%B7%D0%BD%D0%B0%D1%82%D1%8C-%D0%BE-%D0%B4%D1%80%D0%B5%D0%B2%D0%BE%D0%B2%D0%B8%D0%B4%D0%BD%D1%8B%D1%85-%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0%D1%85-%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85-d750444a77ec

Виды:

• Сбалансированные/Несбалансированные
• Бинарные - иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей)
• Красно-черные деревья (балансируют себя сами)
• АВЛ-Дерево (AVL tree)
• ДБ-Дерево
• Сплей-Дерево (Splay tree)

• https://www.geeksforgeeks.org/heap-data-structure/

• https://www.javatpoint.com/binary-tree

Двоичное дерево — это нелинейная структура данных древовидного типа, которая в основном используется для сортировки и поиска, поскольку они хранят данные в иерархической форме (hierarchical form). Самый верхний узел называется корневым узлом (root). В бинарном дереве узел содержит данные и указатель (адрес) левого и правого дочерних узлов (left and right pointers).

• https://www.javatpoint.com/binary-search-tree

Двоичное дерево поиска - это вид двоичного дерева, который следует некоторому порядку расположения элементов. В двоичном дереве поиска значение левого узла должно быть меньше родительского узла, а значение правого узла должно быть больше родительского узла. Это правило применяется рекурсивно к левому и правому поддеревьям корня.

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

Преимущества BST (Бинарного поиска дерева):

• Поиск элемента в двоичном дереве поиска прост, так как у нас всегда есть подсказка, в каком поддереве находится нужный элемент.
• По сравнению с массивом и связанными списками операции вставки и удаления в BST выполняются быстрее.

• https://www.javatpoint.com/avl-tree

Дерево AVL было изобретено GM Adelson-Velsky и EM Landis в 1962 году. Дерево названо AVL в честь его изобретателей.

Дерево AVL можно определить как сбалансированное по высоте двоичное дерево поиска (height), в котором каждый узел связан с коэффициентом баланса, который рассчитывается путем вычитания высоты его правого поддерева из высоты его левого поддерева.

Говорят, что дерево сбалансировано, если коэффициент баланса каждого узла находится в диапазоне от -1 до 1, в противном случае дерево будет несбалансированным и его необходимо будет сбалансировать.

Balance Factor (k) = height (left(k)) - height (right(k))

Вращения AVL (AVL Rotations) — это операции, которые выполняются на деревьях AVL для поддержания их баланса.

• https://www.javatpoint.com/red-black-tree

Red Black Tree — это особый тип бинарного дерева поиска с самобалансирующимся поведением (self-balancing behavior). Каждый узел (node) красно-черного дерева имеет дополнительный бит, который всегда интерпретируется как цвет. Для сохранения баланса красно-черного дерева при вставке, обновлении и удалении используются эти красный и черный цвета.

Self-balancing - сбалансированные по высоте бинарные деревья поиска, которые автоматически поддерживают минимально возможную высоту при выполнении операций вставки и удаления в дереве.

Характеристики красного-черного дерева:

• У каждого нода должен быть цвет красный или черный
• Root node (корневой узел) должен быть всегда черным
• У красного узла не должно быть родителя и потомка красного цвета
• Каждый путь от узла к любому из узлов NULL его потомков имеет одинаковое количество черных узлов.

• https://www.javatpoint.com/splay-tree

Splay tree — это самонастраивающаяся структура данных двоичного дерева поиска, что означает, что древовидная структура динамически настраивается на основе доступных или вставленных элементов. Другими словами, дерево автоматически реорганизуется так, что часто используемые или вставляемые элементы становятся ближе к корневому узлу.

• https://www.javatpoint.com/b-tree

B-дерево — это специализированное дерево m-way (Multiway tree), которое можно широко использовать для доступа к диску. B-дерево порядка m может иметь не более m-1 ключей и m дочерних элементов. Одной из основных причин использования B-дерева является его способность хранить большое количество ключей в одном узле и большие значения ключей за счет относительно небольшой высоты дерева.

Многопутевое дерево (Multiway tree) определяется как дерево, которое может иметь более двух дочерних элементов. Если многопутевое дерево может иметь максимум m потомков, то такое дерево называется многопутевым деревом порядка m (или m-ветвевым деревом).

Преимущества Multiway trees:

• Эффективное использование хранилища. Многоходовые деревья предназначены для эффективного использования пространства хранения, особенно при хранении больших объемов данных. Это связано с тем, что они хранят несколько значений в каждом узле, что позволяет им хранить большое количество элементов, используя относительно небольшое количество узлов.
• Быстрый доступ: Многоходовые деревья имеют быстрое время доступа, особенно для больших наборов данных. Это связано с тем, что они разработаны таким образом, чтобы высота дерева была как можно меньше, что уменьшает количество операций, необходимых для доступа к определенному элементу.
• Эффективный поиск и вставка. Многоходовые деревья предназначены для обеспечения эффективных операций поиска и вставки даже при увеличении размера набора данных. Это связано с тем, что они предназначены для самобалансировки, что гарантирует, что дерево останется сбалансированным и эффективным даже при добавлении или удалении новых элементов.
• Хорошая производительность дискового хранилища. Многоканальные деревья особенно полезны для хранения данных в дисковом хранилище, например в базах данных или файловых системах. Это связано с тем, что они сводят к минимуму количество обращений к диску, необходимых для извлечения определенного элемента, что необходимо для эффективной работы при работе с большими наборами данных.
• Универсальность. Многоходовые деревья можно использовать в самых разных приложениях, от файловых систем до баз данных и поисковых систем. Это делает их универсальной структурой данных, которую можно использовать в различных контекстах.

Список основных сортировок:

• Selection sort - O(n2)
• Bubble sort - O(n2)
• Insertion sort - O(n2)
• Quick sort - O(n*log(n))
• Merger sort - O(n*log(n))

Основные алгоритмы сортировки в деталях:

• Bubble Sort (Пузырьковая сортировка). Сложность - O(n2)
  Самый простой алгоритм сортировки. Алгоритм сравниваем соседние элементы в массиве и меняет их местами в соответствии с результатом сравнения. Пузырьковая сортировка характеризуется низкой производительностью.
  https://github.com/Azatick94/Java_Learning/blob/main/Basic_Java/src/main/java/learning_questions_answering/sorting_algorithms/Bubble_Sort.java
  

• Selection Sort (Сортировка методом выбора). Сложность - O(n2) Один из простейших способов сортировки.
  Порядок работы алгоритма:

1. Находим наименьший элемент в массиве и меняем его с первым элементом в массиве.
2. Далее находим следующий наименьший элемент или меняем его со вторым элементом в массиве.
3. Продолжаем процесс до последнего элемента в массиве. alt text

• Insertion Sort (Сортировка методом вставки) Алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступающий элемент размещается в подходящее место среди ранее упорядоченных элементов.

  Сортировка вставками — еще один очень известный алгоритм сортировки, и он работает так, как вы бы сортировали элементы в реальной жизни. Он выполняет итерацию по заданному массиву, выясняет, какова правильная позиция каждого элемента, и вставляет каждый элемент на свое место.

  
  https://www.educative.io/answers/what-is-insertion-sort-in-java
  

alt text

• Quick Sort (Быстрая сортировка). Сложность - 0(n*log(n))
  Эффективный способ сортировки. Quick Sort - "Divide and Conquer" алгоритм (Разделяй и властвуй). Quick sort использует рекурсия для сортировки. Ссылка на статью
  

Quick sort Explained. alt text

• Merger Sort (Сортировка методом объединения). Сложность - O(n*logn). Алгоритм типа Разделяй и Властвуй. Алгоритм каждый раз разбивает массив на два массива. И так на каждом этапе разбивает древовидно до массивов с одним элементом. Далее происходит создание массива с упорядоченным порядком элементов. alt text

Также существуют много других алгоритмов:

• Heap Sort;
• Counting Sort;
• Radix Sort;
• Bucket Sort;

Проходимся по каждому элементу один за другим. Когда элемент, который вы ищете, найден, возвращаем его индекс.

• https://www.geeksforgeeks.org/binary-search/
• https://github.com/Azatick94/Java_Learning/tree/main/Basic_Java/src/main/java/learning_questions_answering/java_core/algorithms/searching/BinarySearch.java

Ключевая идея проста. Предполагая, что входной массив отсортирован, сравнивается искомый элемент с элементом в середине массива. Если искомый элемент больше, чем элемент в середине массива, рекурсивно проверьте его во второй половине данного массива. В противном случае ищите его в первой половине заданного массива.

• https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/

• https://github.com/Azatick94/Java_Learning/tree/main/Basic_Java/src/main/java/learning_questions_answering/java_core/algorithms/string_manipulations/pattern_searching/NaivePatternSearchingAlgorithm.java

• Это самый простой метод, который использует подход грубой силы.

• Это прямой подход к решению проблемы.

• Он сравнивает первый символ шаблона с доступным для поиска текстом. Если совпадение найдено, указатели в обеих строках продвигаются вперед. Если совпадение не найдено, указатель текста увеличивается, а указатель шаблона сбрасывается. Этот процесс повторяется до конца текста.

• Он не требует какой-либо предварительной обработки. Он сразу начинает сравнивать обе строки посимвольно.

• Временная сложность = O(m * (n-m))

• https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/?ref=rp

TODO

Это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование. Он был разработан в 1987 году Михаэлем Рабином и Ричардом Карпом.

Как известно, алгоритм наивного сопоставления строк перемещает шаблон один за другим. После каждого слайда поочередно проверяет символы на текущей смене, и если все символы совпадают, то печатает совпадение. Подобно наивному алгоритму, алгоритм Рабина-Карпа также сдвигает шаблоны один за другим. Но в отличие от Наивного алгоритма алгоритм Рабина-Карпа сопоставляет хеш-значение шаблона с хеш-значением текущей подстроки текста, и если хэш-значения совпадают, то только тогда начинает сопоставлять отдельные символы. Таким образом, алгоритм Рабина Карпа должен вычислять хеш-значения для следующих строк.

Таким образом, должна использоваться хэш-функция. Хеш-функция, предложенная Рабином и Карпом, вычисляет целочисленное значение. Целочисленное значение строки — это числовое значение строки.

TODO

• https://en.wikipedia.org/wiki/Breadth-first_search

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

• Если ли путь от ноды A в ноду B
• Какой самый быстрый путь от ноды А в ноду B.