Поиск в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Учитывая повернутый отсортированный массив nums и число (target), которое надо найти, алгоритм должен возвращать индекс target в пределах nums или -1, если он отсутствует. Предполагается, что все элементы в отсортированном повернутом массиве уникальны.

Решение, работающее за время O(n), тривиально, поэтому реализацию должна быть за время O(log n).

Пример 1: Input: nums = [3,4,5,6,1,2], target = 1
Output: 4

Пример 2: Input: nums = [3,5,6,0,1,2], target = 4
Output: -1

Медиана двух отсортированных массивов

Проблема: Даны два целочисленных массива nums1 и nums2 размера m и n соответственно, каждый из которых отсортирован в порядке возрастания. Необходимо реализовать алгоритм, который возвращает медианное значение среди всех элементов двух массивов.

Медиана набора чисел — это значение, отделяющее верхнюю половину от нижней половины данных.

Решение работает за O(log(m+n)) времени.

Пример 1: Input: nums1 = [1,2], nums2 = [3]
Output: 2.0

Пример 2: Input: nums1 = [1,3], nums2 = [2,4]
Output: 2.5

Найти повторяющееся число

Проблема: Дан массив целых чисел nums, содержащий n + 1 целое число. Каждое целое число в nums находится в диапазоне [1, n] включительно.

Каждое целое число встречается ровно один раз, за ​​исключением одного целого числа, которое встречается два или более раз. Необходимо реализовать алгоритм, который возвращает число, которое встречается более одного раза.

Решение не изменяет числа массива и использует O(1) дополнительное пространство.

Один из наиболее эффективных методов использует идею цикла (tortoise and hare), аналогичную той, которая используется в проблеме обнаружения цикла в связном списке.

Пример 1: Input: nums = [1,2,3,2,2]
Output: 2

Пример 2: Input: nums = [1,2,3,4,4]
Output: 4

Вес последнего камня

Проблема: Дан массив целых чисел, где Stones[i] представляет вес i-го камня.
Представим, что мы играем в игру с камнями. На каждом ходу выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют вес x и y, причем x <= y.

Результат удара может быть:
- Если x == y, оба камня уничтожаются, и
- Если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x.

В конце игры остается не более одного камня. Необходимо реализовать алгоритм, который возвращает вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример: Input: stones = [2,3,6,2,4]
Output: 1

K-й самый большой элемент в массиве

Проблема: Дан несортированный массив целых чисел nums и целое число k. Необходимо реализовать алгоритм, который возвращает k-й по величине элемент массива.

Под k-м самым большим элементом мы подразумеваем k-й самый большой элемент в отсортированном порядке, а не k-й отдельный элемент.

В решение не используется сортировка.

Пример:
Input: nums = [2,3,1,1,5,5,4], k = 3
Output: 4

Линейная регрессия (Linear regression)

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

Цель линейной регрессии — поиск линии, которая наилучшим образом соответствует этим точкам.

Модель линейной регрессии выглядит следующим образом:
Y = aX + b, где:
X — независимая переменная,
Y — зависимая переменная (предсказываемое значение),
a — коэффициент наклона,
b — смещение (пересечение с осью Y).

Для оценки точности регрессии используют разные метрики, например MSE (mean squared error — средняя квадратическая ошибка). Чем ниже MSE, тем лучше модель.

Матричный метод линейной регрессии

Этот метод находит широкое применение в различных сферах жизни и бизнеса для анализа данных, например:

1. Финансовый анализ и прогнозирование
- Оценка рыночных рисков и доходностей.
- Прогнозирование цен на жилье.

2. Медицина и здравоохранение
- Оценка влияния факторов на здоровье.
- Анализ и прогнозирование медицинских затрат.

3. Маркетинг и бизнес-аналитика
- Прогнозирование спроса на товары и услуги.
- Анализ поведения клиентов.

4. Индустрия развлечений
- Рекомендательные системы.
- Прогнозирование кассовых сборов фильмов.

Полиномиальная регрессия

Это расширение линейной регрессии, которое позволяет моделировать более сложные зависимости между независимой переменной X и зависимой переменной Y. В отличие от линейной регрессии, где мы предполагаем линейную зависимость, полиномиальная регрессия использует полиномиальные функции для описания связи между переменными.

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

Логистическая регрессия

Это статистический метод, используемый для моделирования зависимости между одной или несколькими независимыми переменными и бинарной зависимой переменной (например, "да/нет", "1/0", "успех/неудача"). Этот метод особенно полезен в задачах классификации, где необходимо предсказать вероятность принадлежности объекта к одной из категорий.

Применение логистической регрессии:

- Классификация: Логистическая регрессия часто используется для классификации объектов на две категории. Например, предсказание, будет ли клиент купить продукт или нет, на основе его характеристик.

- Медицинские исследования: В медицине логистическая регрессия используется для предсказания вероятности заболевания (например, наличие или отсутствие болезни на основе различных факторов).

- Социальные науки: Применяется для анализа данных, где исследуется влияние различных факторов на бинарный результат (например, выборы, респонденты, ответившие "да" или "нет").

Метод опорных векторов

SVM (Support Vector Machine) — это алгоритм машинного обучения, используемый для задач классификации и регрессии. Он работает на основе нахождения гиперплоскости, которая наилучшим образом разделяет данные на различные классы.

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

Задача SVM заключается в нахождении гиперплоскости, которая максимизирует расстояние (зазор) между ближайшими точками разных классов. Эти ближайшие точки называются опорными векторами.

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

SVM с линейным ядром

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

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

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

Зазор (margin) - это расстояние между гиперплоскостью и ближайшими точками каждого класса. Задача SVM заключается в максимизации этого зазора.

Есть два типа зазора:
1. Классификация с жёстким зазором (hard margin), когда все обучающие образцы должны быть правильно классифицированы и находиться за пределами полосы разделения.
2. Классификация с мягким зазором (soft margin), когда вводится допущение, что некоторые обучающие образцы могут нарушать условие правильной классификации или попадать в полосу разделения

SVM с полиномиальным ядром

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

Влияние гиперпараметров
- Степень полинома d: Чем выше степень, тем более сложной становится граница между классами. При высоких значениях степень модели может стать излишне сложной и переобучиться.
- 𝛾: Этот параметр регулирует влияние отдельных признаков. Если γ слишком велико, модель может плохо обобщаться на новых данных.
- c0: Этот параметр смещает границу принятия решения, добавляя гибкость при нахождении разделяющей гиперплоскости.

Когда использовать полиномиальное ядро:
1. Данные содержат признаки, которые имеют полиномиальные зависимости.
2. Линейное ядро не может адекватно разделить классы.
3. Модель требует нелинейной границы, но с более низким уровнем сложности, чем при использовании RBF-ядра.

SVM с RBF ядром

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

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

Когда использовать RBF ядро:
1. Линейные модели или полиномиальные ядра не дают хороших результатов, так как границы между классами слишком сложны.
2. Требуется максимальная гибкость в создании нелинейных границ между классами.
3. Данные имеют высокую сложность, и полиномиальные ядра не могут точно разделить классы.

Алгоритм k-ближайших соседей

k-Nearest Neighbors (k-NN) — это метод машинного обучения, основанный на принципе нахождения k ближайших точек данных (соседей) в пространстве признаков, которые наиболее близки к новой точке, и на их основе делается предсказание.

Алгоритм k-NN не строит модели и не использует обучение в привычном смысле. Вместо этого он просто сохраняет все тренировочные данные и использует их для предсказаний.

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

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

Найдя расстояние до всех точек в тренировочных данных, алгоритм выбирает 𝑘 ближайших соседей.

Метод случайного леса

Случайный лес (Random Forest) — это ансамблевый метод машинного обучения, который строит несколько деревьев решений и объединяет их предсказания для получения более точного результата.

В основе метода лежит идея бэггинга (Bootstrap Aggregating), где каждое дерево обучается на случайной подвыборке данных с возвращением. Кроме того, случайный лес вносит дополнительную случайность, выбирая случайное подмножество признаков при каждом разбиении узла дерева.

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

Ридж-регрессия

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

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

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

Лассо-регрессия

Lasso Regression — это метод линейной регрессии, который включает регуляризацию для уменьшения сложности модели и предотвращения переобучения. Название "Лассо" происходит от "Least Absolute Shrinkage and Selection Operator", что подчеркивает две основные функции этого метода: сжатие коэффициентов и отбор признаков.

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

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

Задача о рюкзаке

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

Алгоритм:
1. Создаем двумерный массив размером
2. Заполняем первую строку массива нулями.
3. Для каждого предмета, начиная с первого и до n-го, проходим по всем возможным вместимостям рюкзака от 0 до W:
- Если текущий предмет можно положить в рюкзак, то выбираем максимальное значение между суммой стоимости текущего предмета и стоимостью предметов, которые можно положить в рюкзак с ограниченной вместимостью.
- Если текущий предмет нельзя положить в рюкзак, то значение остается таким же, как и в предыдущей ячейке массива.
4. Значение в последней ячейке массива будет являться оптимальной стоимостью предметов в рюкзаке.
5. Чтобы восстановить решение, начиная с последней ячейки, проверяем, было ли значение обновлено.

Сложность: O(nW), где n - число предметов, а W - вместимость рюкзака.

Код Хаффмана

Метод без потерь для сжатия данных, который использует переменную длину кодирования. Он был разработан Дэвидом Хаффманом в 1952 году.

Алгоритм:
1. Создаем таблицу частот символов в исходном наборе данных.
2. Создаем листы дерева для каждого символа на основе их частоты, присваивая символам коды длиной 1.
3. Повторяем следующие шаги до тех пор, пока не будет создано дерево:
а. Выбираем два узла с наименьшей частотой и создаем новый узел-родитель.
б. Присваиваем новому узлу суммарную частоту своих потомков.
в. Дополняем левому потомку кодом "0" и правому потомку кодом "1".
4. Повторяем шаг 3 до тех пор, пока все узлы не будут объединены в один корневой узел.

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

Эластичная чистая регрессия

Elastic Net — метод линейной регрессии, который сочетает преимущества двух регуляризаций: Лассо (L1) и Риджа (L2). Он помогает справиться с задачей отбора признаков и предотвращает переобучение, особенно когда данные содержат много коррелирующих признаков.

Эластичная сеть использует комбинацию штрафов:
L1-регуляризация (Лассо): способствует разреженности признаков (некоторые коэффициенты становятся нулевыми).
L2-регуляризация (Ридж): снижает величину коэффициентов, предотвращая переобучение.

Когда использовать эластичную чистую регрессию?
- Данные содержат множество признаков, часть из которых сильно коррелирует.
- Требуется и отбор признаков (как у Лассо), и уменьшение коэффициентов (как у Риджа).
- Простая линейная регрессия приводит к переобучению.