Algorithms

	https://neetcode.io/roadmap
	Yandex: Каталог задач на алгоритмы
	Бесплатный курс Подготовка к алгоритмическому собеседованию. Яндекс Практикум
	Яндекс Образование: Хендбук Основы алгоритмов
	ULearn Курс: Оценка сложности алгоритмов
	https://the-algorithms.com/ru
`16.01.2020`	Yandex: Основные виды сортировок и примеры их реализации

`07.10.2013`	https://habr.com/ru/articles/196560/
`29.07.2013`	https://habr.com/ru/articles/188010/

`31.07.2024`	https://youtu.be/REsff9CIR1Q
`26.07.2023`	https://youtu.be/tfvm2k5c9JI
`14.05.2021`	https://youtu.be/aYuAd-IDigc
`11.02.2021`	https://youtu.be/ou5hSWC82To

	https://www.youtube.com/playlist?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`02.06.2021`	https://youtu.be/QLhqYNsPIVo?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`04.06.2021`	https://youtu.be/SKwB41FrGgU?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`07.06.2021`	https://youtu.be/PUpmV2ieIHA?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`09.06.2021`	https://youtu.be/Nb5mW1yWVSs?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`11.06.2021`	https://youtu.be/mdJdB7On4AM?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`14.06.2021`	https://youtu.be/de28y8Dcvkg?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`16.06.2021`	https://youtu.be/YENpZexHfuk?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`18.06.2021`	https://youtu.be/J2C6rDqe8mQ?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`21.06.2021`	https://youtu.be/hGixDBO-p6Q?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`23.06.2021`	https://youtu.be/lEJzqHgyels?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`25.06.2021`	https://youtu.be/fqsuy5rwZhk?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5
`30.06.2021`	https://youtu.be/5lfkBD4dnGM?list=PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5

Временная ложность

Временная сложность измеряет, сколько времени потребуется алгоритму для завершения работы в зависимости от размера входных данных. Она выражается через количество базовых операций (например, сравнение, присваивание), которые выполняются алгоритмом. Временную сложность обычно записывают с использованием нотации O-большое (Big-O), которая описывает верхнюю границу времени выполнения алгоритма по мере увеличения размера входных данных. Временная сложность важна, потому что она помогает оценить, насколько быстро будет выполняться алгоритм на больших объемах данных.

Примеры временной сложности:

• O(1) — Константная сложность: время выполнения не зависит от размера входных данных.

• O(n) — Линейная сложность: время выполнения растет пропорционально размеру входных данных.

• O(n²) — Квадратичная сложность: время выполнения растет пропорционально квадрату размера входных данных.

• O(log n) — Логарифмическая сложность: время выполнения растет пропорционально логарифму от размера входных данных.

Пространственная сложность

Пространственная сложность измеряет, сколько памяти потребуется алгоритму для завершения работы в зависимости от размера входных данных. Она также выражается через нотацию O-большое и описывает верхнюю границу потребления памяти алгоритмом. Пространственная сложность включает память, используемую для хранения входных данных и дополнительную память, требуемую для выполнения алгоритма (например, для хранения временных переменных, рекурсивного стека и т.д.). Пространственная сложность важна, потому что она помогает оценить, сколько памяти потребуется алгоритму, что особенно критично в условиях ограниченных ресурсов.

Примеры пространственной сложности:

• O(1) — Константная сложность: алгоритм использует фиксированное количество памяти, независимо от размера входных данных.

• O(n) — Линейная сложность: память, используемая алгоритмом, растет пропорционально размеру входных данных.

О-Нотация

О-нотация (Big O notation) — это способ описания асимптотической сложности алгоритмов, который показывает, как время выполнения или использование памяти алгоритма изменяется в зависимости от размера входных данных. Она позволяет оценить эффективность алгоритмов и сравнить их производительность.

• Анализ алгоритмов. О-нотация позволяет определить, насколько эффективно работает алгоритм и насколько он масштабируется с увеличением объема данных.

• Сравнение алгоритмов. Позволяет сравнить различные алгоритмы по их эффективности и выбрать наиболее подходящий для конкретной задачи.

• Проектирование. Помогает в разработке алгоритмов и структур данных, чтобы обеспечить их эффективность и производительность.

Концепции

• Асимптотическая сложность. О-нотация выражает поведение алгоритма при стремлении размера входных данных к бесконечности. Она помогает понять, как изменяется сложность алгоритма с увеличением объема данных.

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

Классы

• O(1) — Константное время: Время выполнения алгоритма не зависит от размера входных данных. Например, доступ к элементу массива по индексу имеет сложность O(1).

• O(log n) — Логарифмическое время: Время выполнения алгоритма растет логарифмически по отношению к размеру входных данных. Примером является бинарный поиск в отсортированном массиве.

• O(n) — Линейное время: Время выполнения алгоритма растет пропорционально размеру входных данных. Например, перебор элементов массива имеет сложность O(n).

• O(n log n) — Линейно-логарифмическое время: Время выполнения алгоритма растет быстрее, чем линейное, но медленнее, чем квадратичное. Часто встречается в алгоритмах сортировки, таких как быстрая сортировка и сортировка слиянием.

• O(n²) — Квадратичное время: Время выполнения алгоритма пропорционально квадрату размера входных данных. Примером является пузырьковая сортировка и некоторые алгоритмы поиска пар.

• O(2^n) — Экспоненциальное время: Время выполнения алгоритма растет экспоненциально с увеличением размера входных данных. Такие алгоритмы часто неэффективны для больших данных и могут быть использованы в задачах, где требуется полный перебор, например, в задачах коммивояжера.

• O(n!) — Факториальное время: Время выполнения алгоритма растет очень быстро по сравнению с размером входных данных. Это типично для задач, где требуется перебор всех возможных перестановок, например, в некоторых задачах комбинаторики.

Оптимизация алгоритма

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

Структуры данных

Массивы

Последовательный набор элементов одного типа, доступ к которым осуществляется по индексу. Хранение данных в фиксированном размере, часто используется для реализации других структур данных (например, стека или очереди).

Поиск	O(n) — требуется полный перебор элементов.
Доступ	O(1) — доступ к элементу по индексу.
Удаление	O(n) — удаление элемента требует перемещения оставшихся элементов.

Связанные списки

• Односвязные списки. Состоят из узлов, где каждый узел содержит данные и ссылку на следующий узел.

• Двусвязные списки. Узлы имеют ссылки как на следующий, так и на предыдущий узел.

• Кольцевые списки. Последний узел указывает на первый узел, образуя кольцо.

Поиск	O(n) — необходим полный обход списка для поиска элемента.
Доступ	O(n) — нельзя напрямую получить доступ к элементу, требуется обход.
Удаление	O(n) — поиск элемента требует O(n), удаление узла — O(1) если узел найден.

Стек

Структура данных, работающая по принципу LIFO (Last In First Out), где последний добавленный элемент извлекается первым. Реализация функций отката, обратного обхода, алгоритмов рекурсии.

Поиск	O(n) — в стеке нет прямого доступа к элементам, требуется полный перебор.
Доступ	O(1) — доступ только к верхнему элементу.
Удаление	O(1) — удаление верхнего элемента.

Очередь

Структура данных, работающая по принципу FIFO (First In First Out), где первый добавленный элемент извлекается первым. Реализация задач планирования, обработки задач в порядке их поступления.

Поиск	O(n) — в очереди нет прямого доступа к элементам, требуется полный перебор.
Доступ	O(1) — доступ только к элементу на фронте или в конце (в зависимости от реализации).
Удаление	O(1) — удаление элемента из начала очереди.

Дек (двусторонняя очередь)

Структура данных, которая позволяет добавлять и удалять элементы с обоих концов. Реализация алгоритмов, которые требуют двустороннего доступа к данным.

Поиск	O(n) — в деке нет прямого доступа к элементам, требуется полный перебор.
Доступ	O(1) — доступ к элементам с обоих концов.
Удаление	O(1) — удаление элемента с обоих концов.

Хэш-таблица

Структура данных, использующая хэш-функцию для быстрой вставки, поиска и удаления элементов. Реализация ассоциативных массивов, кэшей, для эффективного поиска данных.

Поиск	O(1) — в среднем, если хорошо распределены хэш-коды и нет большого числа коллизий.
Доступ	O(1) — доступ к элементу по ключу.
Удаление	O(1) — удаление элемента по ключу.

Дерево

Организация данных в иерархии, упорядоченный поиск, реализация кучи (heap).

Бинарное дерево поиска (BST)

Поиск	O(log n) — в сбалансированном дереве; O(n) — в несбалансированном.
Доступ	O(log n) — в сбалансированном дереве.
Удаление	O(log n) — в сбалансированном дереве.

Балансированные деревья (AVL, красно-черное, B-дерево)

Поиск	O(log n) — всегда сбалансировано.
Доступ	O(log n) — всегда сбалансировано.
Удаление	O(log n) — всегда сбалансировано.

Дерево B и B+

Поиск	O(log n) — всегда сбалансировано.
Доступ	O(log n) — всегда сбалансировано.
Удаление	O(log n) — всегда сбалансировано.

Графы

Моделирование сетевых структур, нахождение кратчайших путей, маршрутизация.

Матрица смежности

Поиск	O(n²) — для всех рёбер, если граф плотный.
Доступ	O(1) — проверка наличия ребра между двумя вершинами.
Удаление	O(1) — удаление ребра.

Список смежности

Поиск	O(n + m) — где n — количество вершин, m — количество рёбер.
Доступ	O(d) — где d — степень вершины.
Удаление	O(d) — удаление всех рёбер, инцидентных вершине.

Куча

Специальное дерево, где значения узлов удовлетворяют определенному свойству (макс-куча или мин-куча). Реализация алгоритмов сортировки (сортировка кучей), приоритетных очередей.

Поиск	O(n) — неопределённое место элемента, требуется полный перебор.
Доступ	O(1) — к корню (в случае min- или max-кучи).
Удаление	O(log n) — удаление корня и перестройка кучи.

Trie (Префиксное дерево)

Дерево, используемое для хранения строк, где общие префиксы представляют общие ветви. Поиск строк, автозаполнение, хранение словарей.

Поиск	O(m) — где m — длина строки.
Доступ	O(m) — где m — длина строки.
Удаление	O(m) — где m — длина строки, если нужно удалить конкретную строку.

Бинарный поиск

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

• Время работы бинарного поиска — O(log n), где n — количество элементов в массиве. Это намного быстрее, чем линейный поиск, который работает за O(n).

• Бинарный поиск можно применять только к отсортированным массивам или спискам.

• Благодаря своей эффективности, бинарный поиск часто используется для поиска в больших объемах данных.

Как работает бинарный поиск:

Инициализация границ поиска:
• Вы устанавливаете две границы — левую (left) и правую (right), которые указывают на начало и конец массива.

Проверка среднего элемента:
• Вы вычисляете индекс среднего элемента между left и right. Это элемент с индексом mid = (left + right) / 2.
• Сравниваете значение в середине массива с искомым элементом:
• Если средний элемент равен искомому, вы нашли его и возвращаете индекс.
• Если средний элемент больше искомого, это означает, что искомый элемент должен находиться в левой половине массива. Соответственно, правая граница сдвигается влево: right = mid - 1.
• Если средний элемент меньше искомого, это означает, что искомый элемент находится в правой половине массива. В этом случае левая граница сдвигается вправо: left = mid + 1.

Повторение:
• Вы повторяете шаги с обновленными границами, пока не найдете элемент или пока левая граница не станет больше правой (это означает, что элемента нет в массиве).

Пример:

Предположим, у нас есть отсортированный массив [1, 3, 5, 7, 9, 11, 13], и мы ищем элемент 9.

Начальные границы: left = 0, right = 6 (индексы начала и конца массива).

Считаем mid = (0 + 6) / 2 = 3. Элемент в середине массива равен 7.

7 < 9, поэтому перемещаем левую границу: left = 4.

Теперь границы: left = 4, right = 6. Считаем mid = (4 + 6) / 2 = 5. Элемент в середине равен 11.

11 > 9, значит, перемещаем правую границу: right = 4.

Теперь left = 4, right = 4. Считаем mid = (4 + 4) / 2 = 4. Элемент в середине равен 9, это и есть искомый элемент.

Бинарное дерево

Cтруктура данных, в которой каждый узел имеет не более двух дочерних узлов (левый и правый). Используются для решения различных задач, таких как оптимизация поиска и упорядочивание данных.

• Узел (Node). Каждый узел содержит данные (значение) и ссылки на два дочерних узла (левый и правый).

• Корень (Root). Самый верхний узел дерева, от которого начинается все дерево. У корня нет родительского узла.

• Листовой узел (Leaf Node). Узел, не имеющий дочерних узлов. Листовые узлы находятся в самом нижнем уровне дерева.

• Внутренний узел (Internal Node). Узел, который имеет хотя бы одного дочернего узла.

• Глубина (Depth). Расстояние от корня до узла. Глубина корня равна 0, глубина его детей — 1, и так далее.

• Высота (Height). Максимальная глубина среди всех узлов дерева. Высота листа равна 0, а высота дерева — максимальная глубина среди всех листовых узлов.

Виды бинарных деревьев

• Бинарное дерево поиска (Binary Search Tree, BST). В этом дереве для любого узла значение левого дочернего узла меньше значения узла, а значение правого дочернего узла больше. Это свойство упрощает поиск, вставку и удаление узлов.

• Сбалансированное бинарное дерево. Например, AVL-дерево или красно-черное дерево, где поддерживается балансировка, чтобы обеспечить логарифмическое время поиска, вставки и удаления.

• Дерево отрезков (Segment Tree). Используется для эффективных запросов диапазона и обновлений. Например, для работы с диапазонами в массиве.

• Куча (Heap). Специальное бинарное дерево, которое удовлетворяет свойству кучи. В минимальной куче значение каждого узла меньше или равно значениям его дочерних узлов, а в максимальной куче — больше или равно.

Операции над бинарным деревом

• Вставка (Insertion). Добавление нового узла в дерево с сохранением его свойств. Например, в BST новый узел вставляется в соответствии с его значением, чтобы сохранить порядок.

• Поиск (Search). Поиск узла с определенным значением. В бинарном дереве поиска это делается по сравнению значений и перемещению по левому или правому поддереву.

• Удаление (Deletion). Удаление узла из дерева. Это может быть более сложным процессом, поскольку необходимо поддерживать свойства дерева после удаления узла.

• Обход (Traversal). Проход по всем узлам дерева.

Способы обхода бинарного дерева

• Прямой обход (Pre-order). Посещение корня, затем левого поддерева, затем правого поддерева.

• Средний обход (In-order). Посещение левого поддерева, корня, затем правого поддерева. Этот метод выводит узлы в отсортированном порядке для BST.

• Посредственный обход (Post-order). Посещение левого поддерева, правого поддерева, затем корня.

• Уровневый обход (Level-order). Посещение узлов по уровням от верхнего к нижнему.

Красно-черное дерево

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

Свойства красно-черного дерева

• Каждый узел — либо красный, либо черный.

• Корень дерева всегда черный.

• Все листья (пустые узлы) являются черными.

• Если узел красный, то оба его дочерних узла должны быть черными (то есть два красных узла не могут быть соседними).

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

Операции в красно-черном дереве

• Вставка (Insertion). При вставке нового узла в красно-черное дерево могут возникать нарушения правил. После вставки выполняется серия операций (повороты и перекраска), чтобы восстановить свойства дерева.

• Удаление (Deletion). Удаление узла также может нарушить свойства дерева. После удаления выполняются операции восстановления, включая повороты и перекраску узлов.

• Поиск (Search). Поиск выполняется как в обычном бинарном дереве поиска. В красно-черном дереве поиск эффективен благодаря поддерживаемой сбалансированности.

Алгоритмы Сортировки

Bubble Sort (Пузырьковая сортировка)

Алгоритм проходит по массиву несколько раз. На каждом проходе он сравнивает соседние элементы и меняет их местами, если порядок нарушен. Крупные элементы «всплывают» вверх, как пузырьки, а маленькие — опускаются вниз.

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

• Средний случай: O(n²). При случайно расположенных элементах алгоритм делает примерно n/2 сравнений и обменов на каждом проходе, а таких проходов требуется n.

• Худший случай: O(n²). Если массив отсортирован в обратном порядке, то каждый элемент придется перемещать с самого начала до самого конца. Это потребует максимального числа сравнений и обменов.

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        var swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                // Обмен элементов
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // Если не было обменов, массив отсортирован
        if (!swapped) break
    }
}

fun main() {
    val array = intArrayOf(5, 1, 4, 2, 8)
    bubbleSort(array)
    println(array.joinToString(", "))
}

Shaker Sort (Шейкерная сортировка)

Улучшенная версия пузырьковой сортировки. Алгоритм «встряхивает» массив: сначала идет слева направо, потом обратно — справа налево. Так он быстрее находит и большие, и маленькие элементы.

• Лучший случай: O(n), если массив уже отсортирован. Алгоритм делает один проход и завершает работу, поскольку не было обменов.

• Средний случай: O(n²). В среднем для сортировки требуется n проходов по массиву, и на каждом проходе выполняется n/2 сравнений.

• Худший случай: O(n²), если массив отсортирован в обратном порядке. В этом случае потребуется максимальное количество сравнений и обменов.

fun shakerSort(arr: IntArray) {
    var left = 0
    var right = arr.size - 1
    var swapped: Boolean

    do {
        swapped = false
        // Проход слева направо
        for (i in left until right) {
            if (arr[i] > arr[i + 1]) {
                arr[i] = arr[i + 1].also { arr[i + 1] = arr[i] }
                swapped = true
            }
        }
        right--

        // Проход справа налево
        for (i in right downTo left + 1) {
            if (arr[i] < arr[i - 1]) {
                arr[i] = arr[i - 1].also { arr[i - 1] = arr[i] }
                swapped = true
            }
        }
        left++
    } while (swapped)
}

fun main() {
    val array = intArrayOf(5, 1, 4, 2, 8, 0, 3)
    shakerSort(array)
    println(array.joinToString(", "))
}

Comb Sort (Сортировка расческой)

Улучшенная версия пузырьковой сортировки. Основная идея — устранять проблему «черепашьих обменов», когда небольшие элементы медленно передвигаются к началу массива. Алгоритм использует шаг (gap), который сначала большой, а затем постепенно уменьшается.

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

• Средний случай: O(n² / 2^p), где p — количество уменьшений шага. Это лучше, чем у пузырьковой сортировки, но все еще не так эффективно, как Quick Sort или Merge Sort.

• Худший случай: O(n²). Если шаг уменьшается слишком быстро, алгоритм становится менее эффективным и работает как пузырьковая сортировка.

fun combSort(arr: IntArray) {
    val n = arr.size
    var gap = n
    var swapped = true
    val shrinkFactor = 1.3

    while (gap > 1 || swapped) {
        // Уменьшаем шаг
        gap = (gap / shrinkFactor).toInt().coerceAtLeast(1)
        swapped = false

        // Проходим по массиву с заданным шагом
        for (i in 0 until n - gap) {
            if (arr[i] > arr[i + gap]) {
                arr[i] = arr[i + gap].also { arr[i + gap] = arr[i] }
                swapped = true
            }
        }
    }
}

fun main() {
    val array = intArrayOf(8, 4, 1, 56, 3, -44, 23, -6, 28, 0)
    combSort(array)
    println(array.joinToString(", "))
}

Quick Sort (Быстрая сортировка)

Делит массив на части, выбирает опорный элемент и сортирует их. Меньшие элементы идут влево, большие — вправо. Процесс повторяется рекурсивно, пока весь массив не будет отсортирован.

• Лучший случай: O(n log n). Если на каждом шаге опорный элемент делит массив на две примерно равные части, то количество шагов будет логарифмическим (log n), а каждый шаг требует O(n) операций.

• Средний случай: O(n log n). В среднем опорный элемент делит массив достаточно хорошо, и алгоритм работает быстро.

• Худший случай: O(n²). Если опорный элемент оказывается наибольшим или наименьшим (например, при сортировке уже отсортированного массива), разделение происходит неравномерно, и алгоритм становится медленным.

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1

    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }

    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1
}

fun main() {
    val array = intArrayOf(10, 7, 8, 9, 1, 5)
    quickSort(array, 0, array.size - 1)
    println(array.joinToString(", "))
}

Merge Sort (Сортировка слиянием)

Использует принцип разделяй и властвуй. Он делит массив на две части, рекурсивно сортирует каждую из них, а затем объединяет (сливает) отсортированные части в один отсортированный массив.

• Лучший случай: O(n log n). Даже если массив уже отсортирован, алгоритм делит его на части и выполняет слияние.

• Средний случай: O(n log n). В среднем время работы не меняется, поскольку каждый шаг деления и слияния требует O(n) операций, а глубина рекурсии — O(log n).

• Худший случай: O(n log n). В отличие от Quick Sort, сложность всегда остается O(n log n), независимо от начального состояния массива.

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr

    val middle = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until middle))
    val right = mergeSort(arr.sliceArray(middle until arr.size))

    return merge(left, right)
}

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0
    var j = 0
    val merged = IntArray(left.size + right.size)
    var k = 0

    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            merged[k++] = left[i++]
        } else {
            merged[k++] = right[j++]
        }
    }

    while (i < left.size) merged[k++] = left[i++]
    while (j < right.size) merged[k++] = right[j++]

    return merged
}

fun main() {
    val array = intArrayOf(38, 27, 43, 3, 9, 82, 10)
    val sortedArray = mergeSort(array)
    println(sortedArray.joinToString(", "))
}

LeetCode

№	Level	Problem	Topics
1	Easy	@Two Sum	ArrayHash Table
9	Easy	@Palindrome Number	Math
13	Easy	@Roman to Integer	Hash TableMathString
14	Easy	@Longest Common Prefix	StringTrie
20	Easy	@Valid Parentheses	StackString
21	Easy	@Merge Two Sorted Lists	Linked ListRecursion
26	Easy	@Remove Duplicates from Sorted Array	ArrayTwo Pointers
27	Easy	@Remove Element	ArrayTwo Pointers
28	Easy	@Find the Index of the First Occurrence in a String	StringString MatchingTwo Pointers
35	Easy	@Search Insert Position	ArrayBinary Search
58	Easy	@Length of Last Word	String
66	Easy	@Plus One	ArrayMath
67	Easy	@Add Binary	Bit ManipulationMathSimulationString
69	Easy	@Sqrt(x)	Binary SearchMath
70	Easy	@Climbing Stairs	Dynamic ProgrammingMathMemoization
83	Easy	@Remove Duplicates from Sorted Array	Linked List
88	Easy	@Merge Sorted Array	ArraySortingTwo Pointers
94	Easy	@Binary Tree Inorder Traversal	Binary TreeDepth-First SearchStackTree
100	Easy	@Same Tree	Binary TreeBreadth-First SearchDepth-First SearchTree
101	Easy	@Symmetric Tree	Binary TreeBreadth-First SearchDepth-First SearchTree
104	Easy	@Maximum Depth of Binary Tree	Binary TreeBreadth-First SearchDepth-First SearchTree
108	Easy	@Convert Sorted Array to Binary Search Tree	ArrayBinary Search TreeDivide and ConcuerTree
110	Easy	@Balanced Binary Tree	Binary TreeDepth-First SearchTree
111	Easy	@Minimum Depth of Binary Tree	Binary TreeBreadth-First SearchDepth-First SearchTree
112	Easy	@Path Sum	Binary TreeBreadth-First SearchDepth-First SearchTree
118	Easy	@Pascal's Triangle	ArrayDynamic Programming
119	Easy	@Pascal's Triangle II	ArrayDynamic Programming
121	Easy	@Best Time to Buy and Sell Stock	ArrayDynamic Programming
125	Easy	@Valid Palindrome	StringTwo Pointers
136	Easy	@Single Number	ArrayBit Manipulation
141	Easy	@Linked List Cycle	Hash TableLinked ListTwo Pointers
144	Easy	@Binary Tree Preorder Traversal	Binary TreeDepth-First SearchStackTree
145	Easy	@Binary Tree Postorder Traversal	Binary TreeDepth-First SearchStackTree
160	Easy	@Intersection of Two Linked Lists	Hash TableLinked ListTwo Pointers
168	Easy	@Excel Sheet Column Title	MathString
169	Easy	@Majority Element	ArrayCountingDivide and ConcuerHash TableSorting
171	Easy	@Excel Sheet Column Number	MathString
190	Easy	@Reverse Bits	Bit ManipulationDivide and Concuer
191	Easy	@Number of 1 Bits	Bit ManipulationDivide and Concuer
202	Easy	@Happy Number	Hash TableMathTwo Pointers
203	Easy	@Remove Linked List Elements	Linked ListRecursion
205	Easy	@Isomorphic Strings	Hash TableString
206	Easy	@Reverse Linked List	Linked ListRecursion
217	Easy	@Contains Duplicate	ArrayHash TableSorting
219	Easy	@Contains Duplicate II	ArrayHash TableSliding Window
222	Easy	@Count Complete Tree Nodes	Binary SearchBinary TreeBit ManipulationTree
226	Easy	@Invert Binary Tree	Binary TreeBreadth-First SearchDepth-First SearchTree
228	Easy	@Summary Ranges	Array
231	Easy	@Power of Two	Bit ManipulationMathRecursion
234	Easy	@Palindrome Linked List	Linked ListRecursionStackTwo Pointers
242	Easy	@Valid Anagram	Hash TableSortingString
257	Easy	@Binary Tree Paths	BacktrackingBinary TreeDepth-First SearchStringTree
258	Easy	@Add Digits	MathNumber TheorySimulation
263	Easy	@Ugly Number	Math
268	Easy	@Missing Number	ArrayBinary SearchBit ManipulationHash TableMathSorting
278	Easy	@First Bad Version	Binary SearchInteractive
283	Easy	@Move Zeroes	ArrayTwo Pointers
290	Easy	@Word Pattern	Hash TableString
292	Easy	@Nim Game	BrainteaserGame TheoryMath
303	Easy	@Range Sum Query - Immutable	ArrayDesignPrefix Sum
326	Easy	@Power of Three	MathRecursion
338	Easy	@Counting Bits	Bit ManipulationDynamic Programming
342	Easy	@Power of Four	Bit ManipulationMathRecursion
344	Easy	@Reverse String	StringTwo Pointers
345	Easy	@Reverse Vowels of a String	StringTwo Pointers
349	Easy	@Intersection of Two Arrays	ArrayBinary SearchHash TableSortingTwo Pointers
350	Easy	@Intersection of Two Arrays II	ArrayBinary SearchHash TableSortingTwo Pointers
367	Easy	@Valid Perfect Square	Binary SearchMath
374	Easy	@Guess Number Higher or Lower	Binary SearchInteractive
383	Easy	@Ransom Note	CountingHash TableString
387	Easy	@First Unique Character in a String	CountingHash TableQueueString
389	Easy	@Find the Difference	Bit ManipulationHash TableSortingString
392	Easy	@Is Subsequence	Dynamic ProgrammingStringTwo Pointers
404	Easy	@Sum of Left Leaves	Binary TreeBreadth-First SearchDepth-First SearchTree
405	Easy	@Convert a Number to Hexadecimal	Bit ManipulationMath
409	Easy	@Longest Palindrome	GreedyHash TableString
412	Easy	@Fizz Buzz	MathSimulationString
414	Easy	@Third Maximum Number	ArraySorting
415	Easy	@Add Strings	MathSimulationString
434	Easy	@Number of Segments in a String	String
441	Easy	@Arranging Coins	Binary SearchMath
448	Easy	@Find All Numbers Disappeared in an Array	ArrayHash Table
455	Easy	@Assign Cookies	ArrayGreedySortingTwo Pointers
459	Easy	@Repeated Substring Pattern	StringString Matching
461	Easy	@Hamming Distance	Bit Manipulation
476	Easy	@Number Complement	Bit Manipulation
482	Easy	@License Key Formatting	String
485	Easy	@Max Consecutive Ones	Array
492	Easy	@Construct the Rectangle	Math
495	Easy	@Teemo Attacking	ArraySimulation
496	Easy	@Next Greater Element I	ArrayHash TableMonotonic StackStack
500	Easy	@Keyboard Row	ArrayHash TableString
1365	Easy	@How Many Numbers Are Smaller Than the Current Number	ArrayCountingHash TableSorting
1480	Easy	@Running Sum of 1d Array	ArrayPrefix Sum
1748	Easy	@Sum of Unique Elements	ArrayCountingHash Table

Two Sum

Palindrome Number

Roman to Integer

Longest Common Prefix

Valid Parentheses

Merge Two Sorted Lists

Remove Duplicates from Sorted Array

Remove Element

Find the Index of the First Occurrence in a String

Search Insert Position

Remove Duplicates from Sorted List

Merge Sorted Array

Binary Tree Inorder Traversal

Same Tree

Symmetric Tree

Maximum Depth of Binary Tree

Convert Sorted Array to Binary Search Tree

Balanced Binary Tree

Minimum Depth of Binary Tree

Path Sum

Pascal's Triangle

Pascal's Triangle II

Best Time to Buy and Sell Stock

Valid Palindrome

Single Number

Linked List Cycle

Binary Tree Preorder Traversal

Binary Tree Postorder Traversal

Intersection of Two Linked Lists

Excel Sheet Column Title

Majority Element

Excel Sheet Column Number

Reverse Bits

Number of 1 Bits

Happy Number

Remove Linked List Elements

Isomorphic Strings

Reverse Linked List

Contains Duplicate

Contains Duplicate II

Count Complete Tree Nodes

Invert Binary Tree

Summary Ranges

Power of Two

Palindrome Linked List

Range Sum Query - Immutable

Reverse Vowels of a String

Intersection of Two Arrays

Intersection of Two Arrays II

Valid Perfect Square

Guess Number Higher or Lower

Ransom Note

First Unique Character in a String

Find the Difference

Is Subsequence

Sum of Left Leaves

Convert a Number to Hexadecimal

Number of Segments in a String

Arranging Coins

Find All Numbers Disappeared in an Array

Assign Cookies

Repeated Substring Pattern

Hamming Distance

Number Complement

License Key Formatting

Max Consecutive Ones

Construct the Rectangle

Teemo Attacking

Next Greater Element I

Keyboard Row

How Many Numbers Are Smaller Than the Current Number

Running Sum of 1d Array

Sum of Unique Elements

Вопросы на собесе (10)

Для чего мы производим оценку сложности алгоритмов?
Оценка сложности алгоритмов позволяет понять, насколько эффективно он будет работать при увеличении объёма входных данных. Это помогает выбрать оптимальные решения, предсказать время выполнения и потребление ресурсов, а также сравнивать разные алгоритмы для решения одной задачи.

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

Объясни разницу между сортировкой пузырьком, вставками, слиянием и быстрой сортировкой. Каковы их временные сложности?
• Пузырьковая сортировка: Сравнение и обмен соседних элементов, пока массив не отсортирован. Время: O(n²).
• Сортировка вставками: Постепенное вставление элементов в отсортированную часть массива. Время: O(n²) в худшем случае.
• Сортировка слиянием: Деление массива на части, сортировка и слияние. Время: O(n log n).
• Быстрая сортировка: Разделение массива по опорному элементу и рекурсивная сортировка частей. Время: O(n log n) в среднем случае, O(n²) в худшем.

В чем разница между массивом и связным списком?
Массив обеспечивает быстрый доступ по индексу, но фиксирован в размере, тогда как связный список динамически расширяется, но имеет медленный доступ к элементам, так как требует обхода списка от начала.

Какая средняя алгоритмическая сложность поиска значения в отсортированном массиве?
O(log n) логарифмическая сложность

Какая средняя алгоритмическая сложность у быстрой сортировки?
O(n log n) логарифмическая сложность

Будет ли график O(n) отличаться от графика O(n+m)?
Да, график O(n) будет отличаться от O(n + m). O(n) растёт линейно в зависимости только от n, тогда как O(n + m) учитывает оба параметра и может расти быстрее, в зависимости от значений n и m.

Будет ли график O(n) отличаться от графика O(n²)?
Да, график O(n) будет отличаться от графика O(n²). График O(n) представляет собой линейный рост, тогда как график O(n²) будет параболическим и расти квадратично. При увеличении n значение O(n²) будет расти значительно быстрее, чем O(n), что приводит к более крутой кривой.

Какая сложность алгоритма?
```
import java.util.LinkedList

var numbers = LinkedList<String>()
numbers.addAll(listOf("1", "2", "3", "4", "5", "6"))

for (i in numbers.size - 1 downTo 0) {
		println("it = ${numbers[i]}") // 2
}
```
Cложность составляет O(n²), так как доступ по индексу в двусвязном списке занимает O(n), а цикл выполняется n раз.

Какая сложность алгоритма?
```
import java.util.ArrayList

var numbers = ArrayList<String>()
numbers.addAll(listOf("1", "2", "3", "4", "5", "6"))

for (i in numbers.size - 1 downTo 0) {
		println("it = ${numbers[i]}") // 2
}
```
Cложность алгоритма составляет O(n), так как доступ к элементам по индексу в ArrayList выполняется за O(1), а цикл проходит по каждому элементу списка один раз.