Как рассчитать вычислительную сложность модели машинного обучения?

Можно говорить как о временной сложности алгоритма, так и о пространственной. Первая описывает количество времени, необходимое для выполнения алгоритма. Вторая — количество необходимой памяти. В ML-моделях это всё зависит от входных данных.

Примем такие обозначения:
n = количество обучающих примеров,
d = количество измерений данных,

Тогда расчёты будут такими:
🔹 KNN
Временная сложность — O(knd) (k — количество соседей)
Пространственная сложность — O(nd)

🔹 Логистическая регрессия
Временная сложность — O(nd)
Пространственная сложность — O(d)

🔹 SVM
Временная сложность (при обучении) — O(n²)
Временная сложность (при запуске) — O(k*d) (k — количество опорных векторов)

🔹 Дерево решений
Временная сложность (при обучении) — O(n*log(n)*d)
Временная сложность (при запуске) — O(максимальная глубина дерева)

Отметим, что это лишь обобщённые оценки.

#машинное_обучение
#программирование

🐍 Задача про умножение матриц

Условие: Вам даны две матрицы, нужно написать функцию для их умножения. Матрицы могут быть квадратными или прямоугольными.

Решение: Напишем решение на чистом Python

def matrix_multiply(A, B):
    # Сначала проверим, можем ли мы вообще перемножить эти матрицы
    if len(A[0]) != len(B):
        raise ValueError("Number of A columns must equal number of B rows.")
    
    # Инициализируем результирующую матрицу, заполненную нулями
    result = [[0 for _ in range(len(B[0]))] for _ in range(len(A))]
    
    # Перемножим матрицы
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                result[i][j] += A[i][k] * B[k][j]
    
    return result

# Проверим функцию на примере
A = [[1, 2, 3],
     [4, 5, 6]]

B = [[7, 8],
     [9, 10],
     [11, 12]]

result = matrix_multiply(A, B)
for row in result:
    print(row)

#программирование
#линейная_алгебра

Напишите код, который будет иллюстрировать Закон больших чисел (ЗБЧ)

ЗБЧ утверждает, что при увеличении количества попыток случайная величина стремится к своему математическому ожиданию. Для иллюстрации возьмём подбрасывание честной монетки. Математическое ожидание выпадения орла равно 0.5. С увеличением числа подбрасываний среднее значение количества выпавших орлов должно приближаться к 0.5.

import random
import matplotlib.pyplot as plt

total_flips = 0
numerical_probability = []
H_count = 0

for i in range(0, 5000):
    new_flip = random.choice(['H', 'T'])  
    total_flips += 1
    if new_flip == 'H':
        H_count += 1
    numerical_probability.append(H_count / total_flips)  

plt.figure(figsize=(10, 6))
plt.plot(numerical_probability, label='Численная вероятность орла')
plt.axhline(y=0.5, color='r', linestyle='-', label='Математическое ожидание (0.5)')
plt.xlabel("Количество бросков")
plt.ylabel("Численная вероятность орла")
plt.title("Закон больших чисел: Подбрасывание монеты")
plt.legend()

plt.show()

#программирование
#теория_вероятностей

Объясните разницу между списком и кортежем?

▫️Список — это упорядоченная коллекция элементов. Элементы могут иметь любой тип. При этом коллекцию можно изменять: вставить новый элемент, удалить старый и т.д. То есть длина у списка динамическая — при необходимости Python будет выделять новую память.
Список создаётся через квадратные скобки.

▫️Кортеж — это тоже упорядоченная коллекция элементов. Элементы тоже могут иметь любой тип. Однако изменять кортеж нельзя. Кроме того, в памяти Python пустой кортеж — всегда в единственном экземпляре. Пустые списки же каждый раз создаются заново.
Кортеж создаётся через круглые скобки.

#программирование
#python

Какие магические методы в Python вы знаете?

Магическими методами в Python называют встроенные методы с двойными подчёркиваниями (например, `__init__`, `__str__`). Они позволяют определять поведение классов для различных операций.

Вот несколько магических методов для примера:
▫️`__init__` — для инициализации нового объекта;
▫️`__del__` — деструктор, который вызывается при удалении объекта;
▫️`__str__` — определяет поведение функции `str()`, вызванной для экземпляра вашего класса;
▫️`__len__` — возвращает длину объекта;
▫️`__eq__` — определяет поведение оператора равенства `==`;
▫️`__iter__` — возвращает итератор для объекта;
▫️`__getitem__` — получение значения по ключу или индексу;
▫️`__call__` — позволяет объекту класса вести себя как функция.

#программирование
#python

Что такое args, kwargs. В каких случаях они требуются?

В Python оператор * используется не только для умножения, но и для того, чтобы «распаковывать» объекты, внутри которых хранятся некие элементы. Именно эта его особенность применяется в случае с args и kwargs. Можно использовать другие имена, но это считается дурным тоном. args — это сокращение от arguments (аргументы), а kwargs — сокращение от keyword arguments (именованные аргументы).

Соответственно, мы используем *args, когда не уверены, сколько аргументов будет передано функции, или если хотим передать список или кортеж аргументов функции. А **kwargs мы используем, когда не знаем, сколько именованных аргументов будет передано функции. В последнем случае, в виду того, что речь идёт об именованных аргументах, применяется словарь, где ключ — имя параметра, значение — значение параметра.

#python
#программирование

Что такое генераторы и итераторы в Python?

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

🔹Итераторы реализуют методы __iter__() и __next__(). Метод __iter__() возвращает сам итератор, а __next__() — следующий элемент коллекции. Если элементы заканчиваются, __next__() должен вызвать исключение StopIteration.

🔹Генераторы представляют собой специальный способ реализации итераторов. Их можно реализовать двумя способами: как функцию с ключевым словом yield или как генераторное выражение. Главное отличие генератора от итератора заключается в том, что значения генерируются по требованию. Каждый раз, когда генератор достигает yield, он возвращает значение и «замирает», сохраняя своё состояние до следующего вызова. Это позволяет использовать меньше памяти при итерации по длинным последовательностям. Канонический пример — генератор, порождающий последовательность чисел Фибоначчи.

#программирование
#python

Напишите функцию для вычисления евклидова расстояния

Вот две точки для примера:

plot1 = [1,3]
plot2 = [2,5]

Решение:

def euclidean_dist(point1, point2):
    return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)**0.5

point1, point2 = [1, 3], [2, 5]
print(euclidean_dist(point1, point2)) # -> 2.23606797749979

#python
#программирование

Что такое JAX?

JAX — это фреймворк для вычислений и исследований в области машинного обучения. Он предоставляет API, совместимое с NumPy, и поддерживает автоматическое дифференцирование, векторизацию, параллелизацию и компиляцию в реальном времени для GPU/TPU. JAX ориентирован на скорость и производительность и подходит для обучения больших моделей, требующих мощных ускорителей.

🔗 Ссылка на документацию JAX

#программирование

Назовите алгоритмическую сложность следующих структур данных: список, словарь, очередь, множество

▪️Список (List)
Позволяет хранить последовательность элементов, поддерживает доступ по индексу.
Операция поиска (доступа к элементу): O(1);
Вставка или удаление элемента: O(n) в худшем случае.

▪️ Словарь (Dictionary)
Позволяет хранить пары «ключ-значение» и обеспечивает быстрый доступ к значениям по ключу.
Операция поиска, вставки и удаления элемента: O(1) в среднем, O(n) в худшем случае при коллизиях.

▪️ Очередь (Queue)
Поддерживает порядок «первым пришёл — первым вышел» (FIFO).
Операция добавления и удаления элемента: O(1).

▪️ Множество (Set)
Хранит уникальные элементы и обеспечивает быстрые операции проверки наличия элемента.
Операция поиска, вставки и удаления элемента: O(1) в среднем, O(n) в худшем случае

#программирование