performance - qué - notación o grande definición y utilidad

¿Es posible que la complejidad del tiempo de cualquier algoritmo disminuya a medida que aumenta el tamaño de la entrada, cualquier ejemplo?

Question

Acabo de leer en el libro de algoritmos de Cormen que big-O y big-omega no siguen la propiedad de la tricotomía. Eso significa que para dos funciones, f(n) y g(n) , puede darse el caso de que no se cumpla f(n) = O(g(n)) ni f(n) = Omega(g(n)) . En el ejemplo, argumentan que si la función es n^(1+sin n) de lo que es posible.

Si bien es correcto, es posible en un algoritmo del mundo real tener un tiempo de ejecución de algo como sin n . Como a veces disminuiría, con el aumento del tamaño de entrada. ¿Alguien sabe alguno de estos algoritmos o puede dar un pequeño fragmento de código que hace esto?

Gracias por las respuestas, por lo que en ese caso es correcto suponer que Dado un problema P con tamaño n, si no se puede resolver en tiempo O (f (n)) por cualquier algoritmo conocido, entonces el límite inferior de P es Omega (f (n)).

Answer 1

El algoritmo de búsqueda de cadenas de Boyer-Moore se vuelve más rápido cuando la cadena buscada se hace más larga. Por supuesto, el factor limitante es más a menudo más bien la longitud de la cadena buscada.

Answer 2

El tiempo de ejecución promedio de SAT para las cláusulas 3CNF generadas aleatoriamente eventualmente disminuye a medida que aumenta la proporción de cláusulas a variables. La intuición es que cuando hay muchas cláusulas en relación con el número de variables, es más probable que la fórmula sea "obviamente" insatisfiable; es decir, los algoritmos típicos de resolución de SAT (uno o dos pasos mejor que una búsqueda exhaustiva, pero lo suficientemente simples como para abarcar un curso de licenciatura) alcanzan rápidamente las contradicciones y se detienen.

Por supuesto, esas son observaciones experimentales para alguna noción de fórmulas 3CNF "aleatorias". No estoy seguro de lo que la gente ha probado al respecto.

Answer 3

Tengo dificultades para concebir un problema significativo con la disminución de la complejidad. Un problema "significativo" tendrá que leer o tocar partes de todas sus entradas. A menos que la entrada se codifique de una manera muy ineficiente, su procesamiento debería tomar una cantidad de tiempo creciente.

Sin embargo, podría estar aumentando hacia una constante.

Answer 4

Utilice cualquier función inversa.

f(x) -> 1 / x
f(x) -> 1 / x²
f(x) -> 1 / log(x)

A medida que crece la entrada x , el valor resultante se reducirá. Es bastante sencillo relacionar un valor menor con un número menor de pasos en el algoritmo. Simplemente use un contador en un bucle para moverse hacia ese número.

Aquí hay un algoritmo simple.

function(x) {
    step = 0.001
    y = 1 / x;
    for (i = 0; i < y; i += step) { /* do something awesome here */ }
}