🙌🏼Вычислительная сложность ML-алгоритмов
Когда объем данных невелик, почти любой ML-алгоритм дает приемлемую точность и подходит для решения соответствующей задачи. Но когда объем и размер данных становятся большими, нужно выбирать для обучения ML-модели такой алгоритм, который не требует слишком много вычислительных ресурсов. Лучше выбрать простой или менее затратный в вычислительном отношении алгоритм, чем алгоритм, требующий больших вычислительных ресурсов, когда точность прогнозирования и сложность выполнения аналогичны или даже немного хуже.
Выбор алгоритма зависит от следующих факторов:
• порядок времени (Time Complexity), необходимого для вычисления алгоритма - функция параметров, связанных с данными, самого алгоритма, объема и количества фич
• сложность вычислительного пространства (Space Complexity) - порядок пространства, требуемый во время вычисления алгоритма - функция параметров, связанных с алгоритмом, таких как количество фичей, коэффициентов, скрытых слоев нейросети. Сложность пространства включает в себя как размер входных данных, так и вспомогательное пространство (Auxiliary Space), используемое алгоритмом во время выполнения;.
Например, сортировка слиянием (Mergesort) имеет вспомогательное пространство 𝑂(𝑛) и пространственную сложность 𝑂(𝑛), а быстрая сортировка (Quicksort) имеет вспомогательное пространство 𝑂(1) и пространственную сложность 𝑂(𝑛). В итоге и сортировка слиянием, и быстрая сортировка имеют временную сложность 𝑂(𝑛log𝑛).
https://medium.com/datadailyread/computational-complexity-of-machine-learning-algorithms-16e7ffcafa7d