¿Cómo juzgar los algoritmos sublineales desde un punto de vista teórico?

Answer 1

Un algoritmo sublineal para el problema de decisión es un resultado imposible o trivial, porque generalmente uno necesita al menos ingresar todo el problema antes de tomar una decisión. Si se puede aceptar una instancia de problema sin examinar toda la entrada, entonces el problema se considera trivial. (Rechazar una instancia antes de examinar toda la entrada no es gran cosa).

Dicho esto, ciertamente hay operaciones de estructura de datos que son tiempo constante, tiempo constante amortizado o tiempo sublineal como [math] O (\ log n) [/ math]. Estos algoritmos no requieren ningún tratamiento teórico especial en comparación con las operaciones que son lineales o superlineales.

Por ejemplo, encontrar el elemento mínimo en un montón es una operación de tiempo constante. Pero el problema de decisión de “¿este árbol constituye un montón” o “es el mínimo de este conjunto de números, al menos N” no puede resolverse en un tiempo sublineal.

Para determinar si una operación de estructura de datos es sublineal, uno simplemente calcula su complejidad temporal, de la manera habitual, y luego la compara con el tamaño de la estructura de datos.