Clasificadores de aprendizaje automático big-O o complejidad

Para evaluar el rendimiento de un nuevo algoritmo clasificador, estoy tratando de comparar la precisión y la complejidad (big-O en entrenamiento y clasificación). De Machine Learning: una revisión obtengo una lista completa de clasificadores supervisados, también una tabla de precisión entre los algoritmos y 44 problemas de prueba del repositorio de datos UCI . Sin embargo, no puedo encontrar una reseña, documento o sitio web con el big-O para clasificadores comunes como:

• C4.5
• RIPPER (creo que esto podría no ser posible, pero quién sabe)
• ANN con propagación hacia atrás
• Bayesiano ingenuo
• K-NN
• SVM

Si alguien tiene alguna expresión para estos clasificadores, será muy útil, gracias.

Sea = número de ejemplos de entrenamiento, d = dimensionalidad de las características yc = número de clases.$N$$d$$c$

Entonces el entrenamiento tiene complejidades:

1. Naive Bayes es , todo lo que necesita hacer es calcular la frecuencia de cada valor de característica d i para cada clase.$O(Nd)$$d_i$
2. -NN está en O ( 1 ) (algunas personas incluso dicen que no existe, pero la complejidad espacial de la capacitación es O ( N d ) ya que necesita almacenar los datos, lo que también lleva tiempo).$k$$\mathcal{O}(1)$$\mathcal{O}(Nd)$
3. SVM no lineal no aproximado es u O ( N 3 ) dependiendo del núcleo. Puede obtener un O ( N 3 ) hasta O ( N 2.3 ) con algunos trucos.$O(N^2)$$O(N^3)$$O(N^3)$$O(N^{2.3})$
4. La SVM aproximada es donde R es el número de iteraciones.$O(NR)$

Pruebas de complejidades:

1. Naive Bayes está en ya que debe recuperar los valores de entidad d para cada una de las clases c .$\mathcal{O}(cd)$$d$$c$
2. $k$$\mathcal{O}(Nd)$

Fuente: "Core Vector Machines: Entrenamiento rápido de SVM en conjuntos de datos muy grandes" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Lo siento, no sé sobre los demás.