Чтобы вычислить K(x, z), вам необходимо:
- Выполнить
O(n) умножения x1 * z1, x2 * x2, ..., xn * zn, - Выполните
O(n) сложения (x1 * z1) + (x2 * x2) + ... + (xn * zn), - Выполните две
O(1) операции _ + c и _ ^ d.
Таким образом, вычисление K(x, z) = (dot(x, z) + c)^d занимает O(n) времени.
Совершенно нормально, что пространство пространственных объектов имеет гораздо более высокую размерность, чем время, необходимое для вычисления ядра: в противном случае нам бы не понадобились ядра в первую очередь, потому что мы могли бы просто вычислить векторы объектов напрямую.
Если вы хотите более экстремальный пример, взгляните на K(x, y) = min(x, y) на неотрицательных действительных числах x, y.Требуется постоянное время для оценки min(x, y).Однако пространство признаков равно L^2(R) (функции, интегрируемые в квадрат на вещественной прямой, со стандартным скалярным произведением в гильбертовом пространстве), а отображение признаков равно phi(x) = chi_{[0, x]}, где chi_{[0, x]} обозначает характеристическую функцию интервала [0, x].Таким образом, пространство признаков бесконечномерно, но время, необходимое для оценки ядра, постоянно.