Временная сложность \(T(n)\) определяет количество операций, которые необходимо выполнить алгоритму для обработки входных данных объемом n.
Показатель сложности усредняется, но на практике необходимо исходить из худшего случая, при котором для обработки входных данных требуется максимальное количество операций. Для этого используется так называемая нотация «O» большое. Грубо говоря, \(O(n)\) выражает доминантный член функции стоимости алгоритма в худшем случае.
Пример из статьи в википедии, демонстрирующий рост числа операций с ростом объема входных данных для алгоритмов разной временной сложности.
Далее в этой статье я попробую собрать данные о временной сложности различных реализаций ML/DL алгоритмов. В статье \(n\) — количество признаков, \(m\) — количество образцов.
Алгоритмы из scikit-learn
Nearest Neighbors Algorithms. Временная сложность зависит от имплементации.
-
brute force (наиболее нативная имплементация, дистанция считается между всеми точками дата-сета). Сложность при построении \(O(n*m^{2})\). Сложность при запросе \(O(n*m)\). Время расчета не зависит от структуры данных и количества «ближайших соседей».
-
K-D tree. Сложность при построении \(O(n*m\log(m))\). Сложность при запросе для небольшого числа фич \(n < 20\) — \(O(n\log(m))\). Для большего числа измерений, сложность возрастает до \(O(n*m)\). Время расчета сильно зависит от структуры данных и растет с увеличением количества «ближайших соседей».
-
Ball Tree. Сложность при построении \(O(n*m\log(m))\). Сложность при запросе — \(O(n\log(m))\). Время расчета сильно зависит от структуры данных и растет с увеличением количества «ближайших соседей».
Больше подробностей смотри в документации
LinearRegression. Временная сложность \(O(m*n^{2,4})\) — \(O(m*n^{3})\) в зависимости от реализации.
SGDClassifier. Временная сложность \(O(m*n)\).
SVC. Временная сложность \(O(m^{2}*n)\) — \(O(m^{3}*n)\). Алгоритм реализован на библиотеке libsvm
LinearSVC. Временная сложность \(O(m*n)\). Алгоритм реализован на базе библиотеки liblinear, который реализует Large Linear Classification (подробнее тут)
DecisionTree. Нахождение оптимального дерева является NP-полной задачей и ее временная сложность \(O(\exp(m))\).
Временная сложность построения сбалансированного бинарного дерева для наивной имплементации \(O(n*m\log(m))\), сложность расчета по построенной модели — \(O(\log(m))\). На практике сбалансированного дерева не получается, поэтому сложность построения дерева возростает до \(O(n*m^{2}\log(m))\). В scikit-learn используется препроцессинг, что позволяет уменьшить итоговую сложность для всего дерева до \(O(n*m\log(m))\). Подробнее.
DecisionTreeClassifier. Обход дерева имеет временную сложность \(O(\frac{\log(m)}{\log(2)})\), ну или \(O(\log{\scriptscriptstyle 2}(m))\). Если осуществляется сравнение по всем признакам, то \(O(n*m\log(m))\), поэтому важно определять количество сравниваемых признаков.
RandomForest. \(O(M*m\log(m))\), где \(M\) — число решающих деревьев. Сложность можно уменьшить с помощью параметров.
Multi-layer Perceptron. \(O(m*n*h^{k}*o*i)\), где \(h\) — количество нейронов, \(k\) — число скрытых слоев, \(o\) — количество выходов и \(i\) — число итераций.
Алгоритмы кластеризации
Affinity Propogation. \(O(n^{2}*t)\), где \(n\) — количество примеров, \(t\) — число итераций до сходимости. Сложность по памяти при этом \(O(n^{2})\)
DBSCAN. \(O(n*d)\), где \(n\) — количество примеров, \(d\) — среднее число соседей. Сложность по памяти при этом линейная \(O(n)\)
OPTICS. \(O(n^2)\)
kMean. Средняя сложность по времени \(O(k*n*t)\), где \(n\) — количество примеров, \(t\) — число итераций до сходимости, \(k\) число соседей. В худшем случае сложность вырастает до \(O(n^{k + \frac{2}{p}})\), где \(p\) число фичей.
MeanShift. При использовании flat или ball tree кернелов, сложность по времени \(O(t*n*\log(n))\), где \(t\) — количество точек кластеризации. В многомерном пространстве сложность стремится к \(O(t*n^2)\).
Статья будет дополняться…
Подробнее о нотации в асимптотическом анализе и про базовые принципы временной сложности