Los algoritmos sublineales generales son algoritmos que se ejecutan en poco o n… pero hay tipos de algoritmos sublineales que son interesantes:
Intuitivamente, los algoritmos sublineales (que no son triviales) son algoritmos que dan algún tipo de respuesta al no mirar toda la entrada. Entonces, si el tamaño de entrada es O (n), entonces el algoritmo solo mira o (n) y da una respuesta.
Un ejemplo típico es la prueba de propiedad. Le da al algoritmo un objeto con alguna estructura (y por lo tanto una propiedad para verificar) y el algoritmo sublineal responde diciendo si el objeto tiene la propiedad o si el objeto está lejos de tenerla. ¡No solo eso, sino que da esta respuesta súper rápida porque responde sin siquiera mirar toda la entrada! Considere el siguiente diagrama:
- ¿Qué significa “un problema claramente establecido es un problema a medio hacer”?
- ¿Hay alguien que haya escrito algo sustancial sobre la resolución de problemas en general?
- Cómo determinar un binario sin signo
- ¿Cuál es el número entero positivo más pequeño [matemática] n [/ matemática], que termina en el dígito [matemática] 6 [/ matemática], de modo que al mover [matemática] 6 [/ matemática] al principio obtienes [matemática] m = 4 \ veces n [/ matemáticas]?
- ¿Qué conjuntos son el subconjunto de cada conjunto?
por lo general, los algoritmos de prueba de propiedad solo pueden ofrecer algún tipo de garantía probabilística. Como nunca miran toda la información, es difícil para ellos dar garantías que sean 100% correctas. Por lo general, si el objeto está realmente lejos de tener la propiedad deseada, entonces es probable que el algoritmo sea correcto (ya que en una probabilidad mayor de 1/2 será correcto, uno puede amplificar el problema volviendo a ejecutar el algoritmo) pero si la entrada es super duper cerca de tener la propiedad, entonces el algoritmo sublineal no ofrece garantías si su respuesta es correcta.
Para concretar las cosas, considere el problema de detectar si una lista está ordenada. Este es un problema bien conocido con un límite inferior bien establecido. Se ejecuta en O (nlogn). Pero en realidad hay un algoritmo sublineal que puede detectar si la entrada está lejos de ser ordenada.
Estos algoritmos son interesantes desde un punto de vista teórico y también desde un punto de vista práctico. Teóricamente es divertido estudiarlos y son interesantes y tienen interesantes algoritmos y matemáticas involucrados en ellos. En la práctica, muchas veces está bien tener una respuesta aproximada y también, el mundo de los “grandes datos”, se vuelve cada vez más importante poder dar respuestas sin mirar todos los datos (ya que puede ser una locura para procesar realmente todo el asunto).
Un interesante ejemplo no trivial de esto es la transformada de Fourier dispersa (Transformación de Fourier rápida dispersa).