Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 1/6
Кратко:
- Численные методы нужны для обучения моделей.
- Вычислительная сложность алгоритма важна для понимания.
- Прямые и итеративные алгоритмы изучаются.
- Метод бисекции также изучается.
- Курс состоит из 6 уроков по 10-15 минут каждый.
Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 2/6
Кратко:
- Вычислительная сложность алгоритмов определяет время работы алгоритма на определенном компьютере.
- Время работы алгоритма зависит от количества выполняемых операций (сложений, умножений, сравнений).
- Время работы алгоритма также зависит от его аргументов (длины списка, числа элементов в списке).
- Вычислительную сложность сложных алгоритмов нельзя вычислить, поэтому используют асимптотическое время работы.
- Асимптотическое время работы показывает, как растет T(n) при увеличении n.
- Если T(n) - многочлен, то асимптотическое время работы равно одночлену наибольшей степени без коэффициента.
- Примеры: линейная сложность (T(n) ~ n), квадратичная сложность (T(n) ~ n²), кубическая сложность (T(n) ~ n³) и константная сложность (T(n) ~ 1).
Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 3/6
Кратко:
- Обучение линейной регрессии - сложная задача.
- Вычислительная сложность расчёта весов зависит от количества объектов (n) и признаков (p).
- Размер матрицы X - n x p, размер вектора y - n.
- Вычислительная сложность T(n, p) зависит от двух параметров: n и p.
- Первое действие в формуле - умножение транспонированной матрицы X на себя.
- Второе действие - нахождение обратной матрицы с кубической сложностью.
- Третье действие - умножение обратной матрицы на транспонированную X.
- Результат предыдущего действия умножается на вектор y.
- Итоговая сложность обучения алгоритма: T(n, p) ~ np².
- Если признаков много, модель будет обучаться долго.
Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 4/6
Кратко:
- Итеративные методы обучения линейной регрессии ускоряют процесс обучения.
- Прямые методы находят точное решение, но их вычислительная сложность не зависит от данных.
- Итеративные методы дают приближенное решение, но их вычислительная сложность зависит от числа шагов.
- Метод бисекции решает уравнение f(x) = 0, если функция непрерывна и у значений на концах отрезка разные знаки.
- Метод бисекции состоит из итераций, на каждой из которых проверяется равенство нулю значения f(x), находится середина отрезка и сравниваются знаки f(x) и f(a), f(b).
- Точность решения обычно задается заранее, и на каждой итерации отрезок с корнем уменьшается в два раза.
- Алгоритм останавливается, когда длина отрезка становится меньше заданной точности.
Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 5/6
Кратко:
- Сравнение методов нахождения корней уравнения.
- Дискриминант квадратного уравнения - b² - 4ac.
- Корни уравнения (x² - x - 2) вычисляются по формуле (-b ± √D)/2a).
- Метод бисекции работает для непрерывных функций.
- Градиентный спуск - ключевой метод для машинного обучения.
- Преимущества градиентного спуска: быстрее на больших наборах данных, применим для линейной регрессии и других функций потерь, подходит для обучения нейронных сетей без прямой формулы.
Спринт 16/24 → Тема 2/8: Анализ алгоритмов → Урок 6/6
Заключение
Теперь вы умеете:
- Находить вычислительную сложность алгоритмов;
- Отличать прямые методы от итеративных;
- Решать уравнения методом бисекции.
Заберите с собой
Чтобы ничего не забыть, скачайте шпаргалку и конспект темы.
В следующей теме вы познакомитесь с алгоритмом градиентного спуска.