Что означает большое O в оптимальных весах KNN?

Вики дает это определение KNN

В распознавании образов алгоритм k-ближайших соседей (k-NN) является
непараметрическим методом, используемым для классификации и регрессии. В обоих
случаях входные данные состоят из k ближайших обучающих примеров в
пространстве признаков. Выход зависит от того, используется ли k-NN для
классификации или регрессии:

• В классификации k-NN выходом является членство в классе. Объект
  классифицируется по большинству голосов его соседей, при этом объект
  назначается к классу, наиболее распространенному среди его k ближайших соседей
  (k – положительное целое число, обычно небольшое). Если k = 1, то объект
  просто назначается к классу этого единственного ближайшего соседа.
• В регрессии k-NN выходом является значение свойства для объекта. Это значение
  является средним значением значений k ближайших соседей.

K-NN является одним из типов обучения на примерах, или ленивого обучения,
где функция аппроксимируется только локально, и все вычисления откладываются
до классификации.

Как для классификации, так и для регрессии полезной техникой может быть присвоение
веса вкладам соседей, так что ближние соседи вносят больший вклад в среднее, чем отдаленные.
Например, одна распространенная схема взвешивания заключается в присвоении каждому
соседу веса 1/d, где d — это расстояние до соседа.

и это объяснение о “Взвешенном классификаторе ближайших соседей”

Классификатор k-ближайших соседей можно рассматривать как присвоение k
ближайшим соседям веса 1/k, а всем остальным – 0. Это можно
обобщить на взвешенные классификаторы ближайших соседей. То есть, где
i-й ближайший сосед получает вес ${\displaystyle
> w_{ni}}$, с ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. Аналогичным
образом также выполняется результат о сильной согласованности взвешенных классификаторов ближайших соседей.

Обозначим $C_{n}^{wnn}$ как взвешенный классификатор ближайших соседей с весами $\{w_{{ni}}\}_{{i=1}}^{n}$.

При соблюдении регулярных условий по распределениям классов избыточный риск имеет следующее асимптотическое разложение
${\mathcal {R}}_{{\mathcal {R}}}(C_{{n}}^{{wnn}})-{\mathcal {R}}_{{{\mathcal {R}}}}(C^{{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$

и эта формула

С оптимальными весами доминирующий член в асимптотическом разложении избыточного риска равен ${\mathcal {O}}(n^{{-{\frac 4{d+4}}}})$

Означает ли $\mathcal {O}$ здесь нотацию “Большое O” или что-то другое?

Чтобы более четко прояснить ответ @Mohith7548, обозначение O() в вашем описании KNN относится к скорости сходимости статистического оценщика. Это не имеет отношения к вычислительной эффективности алгоритмов, а скорее к тому, насколько далеко ожидаются оценки, выводимые алгоритмом KNN, от идеальных оценок (т.е. лучших возможных прогнозов) для выборки размера n и размерности d. По мере роста n до бесконечности оценщик KNN должен сойтись к оптимальному предсказателю (при соблюдении некоторых базовых регулярных условий), и формула O() описывает, как быстро эта сходимость происходит с увеличением n. Сходимость медленнее с высокоразмерными данными, потому что статистическая оценка большего количества чисел сложнее (см. “проклятие размерности”).

Смотрите “сходимость по вероятности“, чтобы узнать больше о этой теме статистических скоростей сходимости (которые отличаются от вычислительной сложности).