7.2.2　分解机的计算复杂度

从式（7-1）来看，因为我们需要处理所有特征交叉，所以计算复杂度是O(kn²)。但是我们通过适当的公式变换并进行简单的数学计算，可以将模型复杂度降低到O(kn)，即变成线性复杂度的预测模型，具体推导过程如下：

从上面推导过程最后一步可以看到，括号里面的复杂度是O(n)，加上外层的，整个计算过程的时间复杂度是O(kn)。进一步，在数据稀疏的情况下，大多数特征x为0，我们只需要对非零的x求和，因此，时间复杂度其实是，是训练样本中平均非零的特征个数。后面会说明对于矩阵分解算法来说，因此对于矩阵分解来说，计算量是非常小的。

由于分解机模型可以在线性时间下计算出结果，对于我们做预测是非常有价值的，特别是对有海量用户的互联网产品，具有极大的应用价值。拿推荐来说，我们每天需要为每个用户计算推荐（这是离线推荐，实时推荐计算量会更大），线性时间复杂度可以让整个计算过程更加高效，在更短的时间完成计算，节省服务器资源。