Масштабируемость (Scalability)

**Определение:** Вычислительная характеристика алгоритма, описывающая асимптотическую зависимость времени работы ($Time$) и потребления оперативной памяти ($Space$) от объема выборки ($n$ объектов и $d$ признаков). **Теоретический аспект (по К.В. Воронцову):** Многие мощные алгоритмы (Spectral, Agglomerative, Affinity Propagation) требуют вычисления и хранения полной матрицы попарных расстояний. Их сложность составляет $O(n^2)$ или $O(n^3)$. При выборках больше 20 000 объектов такие методы исчерпывают оперативную память. **Инженерные решения для Big Data:** Для достижения высокой масштабируемости применяются структурные и алгоритмические оптимизации: * **Пространственные индексы:** KD-деревья или Ball-деревья снижают сложность поиска соседей с $O(n^2)$ до $O(n \log n)$ (например, оптимизированный DBSCAN). * **Пакетная обработка:** Метод градиентного спуска по мини-батчам (MiniBatch K-Means). * **Предагрегация (Сжатие):** Построение компактного дерева признаков за один проход по данным $O(n)$ (алгоритм BIRCH).