Respuesta corta: es un problema P, pero no puedo darle la complejidad computacional exacta
Respuesta larga:
Esta pregunta no tiene una respuesta definitiva. Esto se debe a que en informática no podemos medir la complejidad de un problema , solo podemos medir la complejidad del algoritmo que resuelve el problema. Voy a describir la complejidad de 4 de los más comunes. Para todos los científicos informáticos de núcleo duro que hay por ahí, podrían avergonzarse porque dejaré de lado la mayoría de los detalles técnicos que deben ser ciertos para que mis afirmaciones sean ciertas.
- ¿Cómo obtenemos una suma de 100 agregando solo 7 números primos?
- ¿Cuál es el significado y el beneficio de las variables compartidas en Theano?
- ¿Cómo pruebo o refuto lo siguiente: f (n) = o (g (x)) implica f (n) = O (g (n))?
- ¿Son defectuosos los números complejos?
- ¿Cuál es la mejor manera de aprender geometría algebraica si uno no está interesado en usarlo para propósitos teóricos numéricos, sino más bien para aplicaciones en física teórica e informática teórica?
Al entrenar un algoritmo de clasificación de Bayes, la complejidad es [matemática] O (n) [/ matemática], suponiendo que se den varias cosas (lo más importante es que se le dan los vectores de características).
Un enfoque de regresión logística que utiliza un optimizador L-BFGS dará [math] O (n) [/ math] en la mayoría de los casos, sin embargo, no hay límites en el peor de los casos para este método, por lo que O (n) no siempre se aplica.
Para un clasificador vecino k-más cercano, la complejidad de la clasificación es directamente proporcional al tamaño del conjunto de entrenamiento (es decir, [matemáticas] O (n) [/ matemáticas])
Finalmente, para los solucionadores de programación cuadrática estándar de svms, la complejidad del algoritmo es [matemática] O (n ^ 3) [/ matemática]
