Me gustaría saber cuál es la peor complejidad de tiempo de ejecución de una instrucción switch, suponiendo que tiene n casos.¿Cuál es la complejidad del tiempo de ejecución de una instrucción switch?
Siempre supuse que era O (n). Sin embargo, no sé si los compiladores hacen algo inteligente. Si la respuesta es específica de la implementación, me gustaría saber para los siguientes idiomas:
En el peor de los casos es O (n). A veces (y esto depende del lenguaje y del compilador), se traduce en una tabla de salto (para interruptores "agradables" que no tienen un rango de caso demasiado grande). Entonces eso es O (1).
Si el compilador quiere ser original, puedo pensar en formas en que se puede implementar la complejidad para que sea algo intermedio (por ejemplo, realizar búsqueda binaria en los casos, para logn). Pero en la práctica, obtendrás más tiempo lineal o tiempo constante.
La gran complejidad de una declaración de interruptor no es realmente el punto importante. La notación de Big-O se refiere al rendimiento cuando n aumenta hacia el infinito. Si tiene una declaración de cambio lo suficientemente grande como para que el rendimiento asintótico sea un problema, entonces es demasiado grande y debe ser refactorizado.
Además del problema de legibilidad, en Java y C# creo que pronto alcanzaría algunos límites internos para el tamaño máximo de un único método.
Para las sentencias de conmutación relativamente pequeñas que se invocan a menudo, probablemente sería más informativo medir el rendimiento real de la instrucción switch frente a otros enfoques que podría utilizar en su lugar. Esta medición podría realizarse realizando repetidamente la operación en un bucle.
Para declaraciones de cambio más grandes, sugiero refactorizar para usar un diccionario o estructura de datos similar que tenga aproximadamente O (1) rendimiento incluso si n es muy grande y no tendrá problemas con el tamaño limitado del método.
Si se llama con frecuencia una declaración de cambio de 10 casos, ¿no tendría sentido tratar de entender ¿Cómo funciona internamente? – Fragsworth
Estoy completamente de acuerdo. Cuando obtienes más de 10 casos, pierdes rápidamente la legibilidad y la simplicidad. Usualmente hay una forma mejor y más clara de hacer las cosas. –
@Fragsworth Sí, definitivamente debes tratar de entender cómo funciona internamente. Pero lo único que Big-O le dice es qué tan rápido será con MUCHOS casos, digamos 100+. El argumento de Mark es que hay formas mucho mejores de analizar las partes internas de las instrucciones de conmutación sin mirar su gran O, como la forma en que el compilador la optimiza y cómo se comparará con el uso de otros métodos, como una tabla de búsqueda. –
Los compiladores de C++ pueden convertir instrucciones de conmutación en una tabla de salto (es decir, construir una matriz de desplazamientos de salto, luego tomar el valor y usarlo como un índice en la tabla). Este es O (1).
El compilador C# utiliza un enfoque similar, excepto que puede ensamblar una tabla hash.
El peor caso podría ser O (n), pero al menos para lenguajes como C/C++, Java y C# donde los casos son constantes de tiempo de compilación, a menudo se puede usar una tabla de salto (y muy a menudo se usa) para obtener la complejidad a O (1).
No sé si los lenguajes más dinámicos como PHP o Javascript intentan configurar tablas de salto o no.
Para php, las expresiones de casos no necesitan ser constantes; 'switch (true) {case expr: doSomething(); } 'es válido, incluso si expr no es constante. Es decir, si recuerdo correctamente. Entonces las mesas de salto serían improbables para algo así. – user314104
C con el compilador gcc tiene O (1) para el rango estrecho (tabla de salto) o en el peor O (registro N) para el rango libre (búsqueda binaria).
La respuesta no es solo específica del lenguaje, ni siquiera es específica del compilador. Depende del código real. Algunos compiladores convierten algunas sentencias de cambio en tablas de salto. –
En el otro extremo, los valores pueden hacer que se invoquen otras funciones. En Ruby, por ejemplo, los valores se verifican usando el operador '===', que puede hacer cualquier cosa. Un uso común de esto son las expresiones regulares, que (en ciertos casos) pueden ser muy costosas, por lo que el costo del cambio está dominado por los propios valores, no por la cantidad que hay. – Ken
¿Hay alguna situación en la que podría ser * mayor * que O (n) (para * n * casos en el interruptor)? – FrustratedWithFormsDesigner