¿Qué significa el “límite más ajustado” de un algoritmo?

Answer 1

Supongamos que tiene un problema que es NP-hard, es decir, no existe un algoritmo de tiempo polinómico para resolver el problema exactamente. En aras de la discusión, supongamos que el problema requiere minimizar alguna función. Por ejemplo, en el problema del árbol Steiner, desea encontrar un árbol con una suma mínima de longitudes de borde.

Ahora supongamos que tiene un algoritmo A que brinda una solución aproximada al problema. En el ejemplo anterior, el algoritmo generará un árbol que está lo suficientemente cerca del árbol verdadero.

Ahora querrá obtener algunas garantías para este algoritmo A, que generalmente tienen la siguiente forma: dado cualquier gráfico, el algoritmo A genera un árbol que ha costado como máximo 2 veces el costo del árbol Steiner óptimo. Para obtener tales garantías, debe presentar una prueba que muestre que para cualquier gráfico, la afirmación anterior es cierta.

Sin embargo, incluso después de tener una prueba de este tipo, es posible que el mismo algoritmo siempre genere árboles con un costo no superior a 1,5 veces el costo óptimo, pero su prueba solo puede mostrar el factor de aproximación como 2. Se dice que dicho límite No ser apretado.

Usando esto, podemos definir qué es un límite ajustado: un límite para un algoritmo es ajustado si no existe un límite menor que exista. Dicho de otra manera, un límite es ajustado si hay al menos una instancia del problema, de modo que el límite se satisfaga con igualdad. En nuestro ejemplo anterior, si tenemos al menos un gráfico donde el costo del árbol devuelto por este algoritmo es exactamente 2 veces el costo óptimo, entonces sabemos que no existe ninguna prueba que pueda reducir el factor de aproximación a menos de 2.

Answer 2

¿Qué quiere decir exactamente con “límite más estrecho”?

Si te refieres a ‘límite estrecho’ o exactamente ‘límite estrecho asintótico’, entonces aquí está, cuando el tamaño de la entrada a un algoritmo es un número razonablemente grande, digamos – n, y existen 2 constantes, digamos c1 y c2, de modo que El tiempo de ejecución de los algoritmos está entre c1. f (n) y c2. f (n), entonces decimos que el algoritmo tiene un límite de tiempo de ejecución de f (n). Se denota por la letra griega “theta”. Entonces, digamos que un algoritmo tiene un límite apretado entre c1. ny c2. n, entonces podemos decir que el algoritmo tiene un tiempo de ejecución de big-theta de n.