Библиотека собеса по Data Science | вопросы с собеседований

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



Можно говорить как о временной сложности алгоритма, так и о пространственной. Первая описывает количество времени, необходимое для выполнения алгоритма. Вторая — количество необходимой памяти. В 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(максимальная глубина дерева)



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



#машинное_обучение

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