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.
- ¿Un subconjunto siempre tiene que ser un elemento de un conjunto?
- ¿De cuántas maneras un mosaico [matemático] 2 \ veces n [/ matemático] puede ser en mosaico por cuadrados unitarios y dominó?
- ¿Cómo un par [matemáticas] n [/ matemáticas] personas con ingresos variables de la mejor manera?
- ¿Por qué se usa la base para representar problemas que se pueden resolver en tiempo exponencial el entero 2?
- ¿Cómo saber si una pregunta matemática es una ‘n!’ pregunta o una pregunta ‘n ^ n’
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].