Cómo demostrar que resolver una función es más difícil que otra

Si te refieres a la idea de “dificultad” en informática como una medida de la complejidad computacional, entonces es trivial demostrar que [matemáticas] f (x) = x + 1 [/ matemáticas] es una función más fácil de procesar que [matemáticas] f (x) = \ sqrt {x} [/ matemáticas].

Usaré la notación “big-O” para esto, por lo que vale la pena verificar que si no lo ha encontrado antes (de todos modos será útil). Un recordatorio rápido de la idea: [matemáticas] O (t (n)) [/ matemáticas] es la función que describe el peor caso de tiempo de procesamiento / operaciones para una función determinada. [matemática] t (n) [/ matemática] aquí está la función que se utiliza para describirla. El caso más simple es [matemática] O (1) [/ matemática]: el peor de los casos para determinar si un número binario es par o impar. Esto significa que la operación ocurre en tiempo constante (independientemente del tamaño del número, siempre tomará el mismo tiempo). Otro ejemplo: [matemática] O (n) [/ matemática] es el peor de los casos para buscar un número en una lista no ordenada (donde n es el número de elementos en la lista). Esto se debe a que el algoritmo podría tener que verificar todos los n números antes de encontrar el que estamos buscando (o establece que no está en la lista). Finalmente, [math] O (\ log n) [/ math] es el peor de los casos para usar la Búsqueda Binaria para encontrar un elemento en una lista ordenada, donde n es el número de elementos en la lista.

Ahora que tenemos ese trabajo preliminar fuera del camino, puedo responder la pregunta correctamente.

Voy a suponer por un momento que nos estamos refiriendo a números binarios (ya que este es un problema de computación) solo para que sea más fácil de explicar.

El peor de los casos para [matemática] f (x) = x + 1 [/ matemática] será [matemática] O (1) [/ matemática], porque un procesador de computadora puede agregar uno a un número en una sola operación.

Es un poco más complicado calcular la complejidad de [math] f (x) = \ sqrt {x} [/ math] porque tenemos que especificar cómo se calculará un sqrt. Voy a suponer que estamos usando el método de Newton para encontrar las raíces de una función, que es la siguiente:

Realizar iterativamente:

[matemáticas] x_ {p + 1} = p_n – \ frac {f (p_n)} {f ‘(p_n)} [/ matemáticas]

Hasta que haya alcanzado un grado razonable de precisión.

Entonces, para nuestra función [matemática] f (x) = x ^ 2 – p [/ matemática] (donde p es el número que estamos enraizando), haremos una suposición inicial (puede ser cualquier cosa no muy lejos de la raíz real – hay métodos sobre cómo hacer esto). Luego realizaremos la iteración.

Podemos demostrar que (suponiendo una precisión constante de los cálculos y una aproximación inicial razonable) el peor momento para el método de Newton es [matemática] O ((\ log n) T (n)) [/ matemática] donde [matemática] T (n ) [/ math] es el costo de calcular [math] f (x) / f ‘(x) [/ math] con precisión de n dígitos.

Sabemos que [matemáticas] f (x) = x ^ 2 [/ matemáticas] y [matemáticas] f ‘(x) = 2x [/ matemáticas] por cálculo simple. [matemática] f (x) [/ matemática] y [matemática] f ‘(x) [/ matemática] tienen complejidad [matemática] O (1) [/ matemática] ya que ambas pueden realizarse en tiempo constante para cualquier número.

Por lo tanto:

[matemáticas] T (n) = 1 [/ matemáticas]

Entonces, el peor de los casos es [matemática] O (\ log n) [/ matemática] para el método de Newton, suponiendo que estamos utilizando [matemática] f (x) = x ^ 2 [/ matemática] dada la precisión de n dígitos.

Está bastante claro que para cualquier valor de x, dada una cantidad razonable de precisión en la raíz, será más fácil calcular la respuesta a [matemáticas] f (x) = x + 1 [/ matemáticas] de lo que será a calcular [matemáticas] f (x) = \ sqrt {x} [/ matemáticas].

La “dificultad” es una cuestión subjetiva. Sin embargo, definitivamente puede calcular el tiempo que tardan estas funciones y luego compararlas. Obviamente, f (x) = x + 1 funciona en el tiempo O (1) y sqrt (x) en el tiempo O (sqrt (n)) y, por lo tanto, calcular el primero lleva menos tiempo.

No ‘resuelves’ funciones. Tampoco ‘computa’ expresiones como f (x) = x + 1, eso es solo una definición. Lo que probablemente quiere decir es evaluarlos, por ejemplo, descubrir que f (4) es igual a 5.

Debe proporcionar una medida de lo que quiere decir exactamente con “difícil” antes de poder comenzar a demostrar que una función es más difícil que otra. Por ejemplo, podría calcular la cantidad de pasos que utiliza un algoritmo estándar para evaluar cada expresión.