¿La complejidad de los algoritmos de clasificación está relacionada con la cantidad de suposiciones que hago? ¿Por qué?

Si cambia el problema agregando más suposiciones, entonces está estudiando fundamentalmente un problema diferente (o posiblemente un caso especial). La complejidad de un algoritmo puede cambiar cuando haces esto, pero la complejidad del algoritmo en sí para el problema más general sin esas suposiciones no lo hace. Discutimos algoritmos con respecto a problemas típicamente, no al revés.

Entonces, si agrega suposiciones sobre el problema de clasificación, entonces puede diseñar algoritmos más eficientes para hacer el trabajo, pero cuando hace esto, no está estudiando el mismo problema del que la gente habla llamado problema de clasificación. Es por eso que ser preciso es muy importante. Te sorprendería cuán fundamentalmente diferentes problemas pueden llegar a ser a veces si incluso agregas uno o dos supuestos. Al restringir las instancias de un problema más general que considere, cuanto más especializado se vuelva el problema (y menos aplicable puede ser al problema general, a menos que demuestre un teorema que diga lo contrario para ese problema).

Tenga en cuenta que esto es cierto para la mayoría de las áreas de estudio en Algoritmos, no solo para la clasificación. No sé si podría decir que hay una relación directa ya que sus “suposiciones” requerirían más estructura (matemática) para precisar una relación.

La técnica de representación de complejidad tiene la provisión de especificación de casos de eficiencia de algoritmos como Peor, Mejor, Promedio.

Estos casos no son más que lo que estás mencionando como suposiciones aquí y así es como tiene sentido para mí.

Sin embargo, su pregunta parece estar hablando más sobre los casos de la naturaleza de los datos de entrada y / o la especialización de la declaración del problema en lugar de los casos de rendimiento del algoritmo.