¿Existe algo así como la complejidad de la O-O "negativa"?

Question

Duplicar posibles:
Are there any O(1/n) algorithms?

Esto sólo apareció en mi cabeza sin ninguna razón en particular, y supongo que es una pregunta extraña. ¿Hay algún algoritmo o problema conocido que realmente obtenga más fácil o más rápido para resolver con una entrada más grande? Supongo que si los hay, no sería para cosas como mutaciones o clasificación, sería por problemas de decisión. Tal vez haya algún problema en el que tener una gran cantidad de información hace que sea fácil decidir algo, pero no puedo imaginarme qué.

Si no existe la complejidad negativa, ¿hay alguna prueba de que no puede existir? ¿O es solo que nadie lo ha encontrado todavía?

Answer 1

No, eso no es posible. Dado que se supone que Big-Oh es una aproximación del número de operaciones que realiza un algoritmo en relación con el tamaño de su dominio, entonces no tendría sentido describir un algoritmo como el uso de un número negativo de operaciones.

La sección de definición formal de la wikipedia article realmente define la notación Big-Oh en términos de usar números reales positivos. De modo que, en realidad, ni siquiera hay una prueba porque todo el concepto de Big-Oh no tiene ningún significado en los números reales negativos según la definición formal.

Respuesta corta: No es posible porque la definición lo dice.

Answer 2

No realmente. O (1) es lo mejor que puedes esperar.

Lo más cercano que puedo pensar es la traducción de idiomas, que utiliza grandes conjuntos de datos de frases en el idioma de destino para hacer coincidir fragmentos más pequeños del idioma de origen. Cuanto mayor sea el conjunto de datos, mejor (y hasta cierto punto más rápido) la traducción. Pero eso ni siquiera es O (1).

Answer 3

actualización Sólo para que quede claro, yo estoy responder a esta parte de la pregunta: ¿Hay alguna algoritmos o los problemas conocidos que en realidad más fácil o más rápido para resolver con la entrada más grande?

Como se señaló en respuesta aceptada aquí, hay no algoritmos de trabajo más rápido con la entrada más grande. Are there any O(1/n) algorithms? Incluso un algoritmo como sleep(1/n) tiene que pasar tiempo leyendo su entrada, por lo que su tiempo de ejecución tiene un límite inferior.

En particular, referes autor relativamente simple algoritmo de búsqueda subcadena:
http://en.wikipedia.org/wiki/Horspool

PS pero utilizando término 'complejidad negativo' para este tipo de algoritmos no parece ser razonable para mí.

Answer 4

Bueno, para muchos cálculos como "entrada dada A return f (A)" puede "cachear" los resultados del cálculo (almacenarlos en matriz o mapa), lo que hará el cálculo más rápido con mayor cantidad de valores, SI algunos de esos valores se repiten.

Pero no creo que califique como "complejidad negativa". En este caso, el rendimiento más rápido probablemente cuente como O (1), el peor de los casos será O (N), y el rendimiento promedio estará en algún lugar intermedio.

Esto es algo aplicable a algoritmos de ordenación - algunos de ellos tienen O (N) mejor de los casos la complejidad de escenarios y O (n^2) la complejidad peor caso, en función del estado de los datos a ser ordenados.

Creo que para tener una complejidad negativa, el algoritmo debe devolver el resultado antes de que se le haya pedido calcular el resultado. Es decir. debe estar conectado a una máquina del tiempo y debe poder tratar con el correspondiente "grandfather paradox".

Answer 5

Pensar en un algoritmo que se ejecuta en tiempo negativo, es lo mismo que pensar en el tiempo retrocediendo.

Si el programa comienza a ejecutarse a las 10:30 AM y se detiene a las 10:00 AM sin pasar por la 11:00 AM, acaba de ejecutar con tiempo = O (-1).

=]

Ahora, para la parte matemática:

Si no puede llegar a una secuencia de acciones que se ejecutan hacia atrás en el tiempo (nunca se sabe ... lol), la prueba es bastante simple:

positiveTime = O (-1) significa:

positiveTime < = c * -1, para cualquier C> 0 y n> n0> 0

Tenga en cuenta la restricción "C> 0". No podemos encontrar un número positivo que multiplicado por -1 dará como resultado otro número positivo. Tomando en cuenta que, este es el resultado:

positiveTime < = negativeNumber, para cualquier n> n0> 0

Wich sólo demuestra que no se puede tener un algoritmo con O (-1).

Answer 6

Al igual que con la otra pregunta sobre el algoritmo vacío, esta pregunta es una cuestión de definición más que una cuestión de lo que es posible o imposible. Sin duda, es posible pensar en un modelo de costo para el cual un algoritmo toma O (1/n) tiempo. (Eso no es negativo, por supuesto, sino que disminuye con una entrada más grande.) El algoritmo puede hacer algo como sleep(1/n) como una de las otras respuestas sugeridas. Es cierto que el modelo de costo se rompe cuando n se envía al infinito, pero n nunca se envía al infinito; cada modelo de costo se rompe eventualmente de todos modos. Decir que sleep(1/n) toma el tiempo O (1/n) podría ser muy razonable para un tamaño de entrada que varía de 1 byte a 1 gigabyte. Ese es un rango muy amplio para que la fórmula de complejidad de tiempo sea aplicable.

Por otro lado, la definición más simple y más estándar de complejidad de tiempo utiliza pasos de tiempo de unidad. Es imposible que una función positiva de valores enteros tenga disminuciones asintóticas; lo más pequeño que puede ser es O (1).

Answer 7

No sé si esto encaja bastante pero me recuerda a bittorrent. Cuantas más personas descarguen un archivo, más rápido se aplicará a todos ellos