La gente en la computación se observa a menudo diciendo que un cálculo se lleva a $\operatorname{O}(n^3\log n)$ pasos o que es NP-duro o que no es computable, o que es primitiva recursiva, etc. Tomé un curso que incluía algunas de las cosas sobre el límite entre lo que es computable y lo que no, a lo largo de las líneas de Hartley Rogers libro, pero que no saben nada acerca de la complejidad computacional que implican las cosas bien dentro de los límites de lo que es computable (un tema descuidado por Rogers' libro). Pero estoy curioso acerca de esta pregunta acerca de la aritmética.
Un ejemplo: Digamos que estoy enfrentado con el problema de encontrar la factorización prima de $667$. A menos que sea el primer en sí, es divisible por un número primo no más grande que su propia raíz cuadrada, y el más grande es $23$. Después de descartar, por diversos medios, la divisibilidad por todos los números primos menos de $23$, considero que uno. Ahora $3$ $7$ son complementarios relativos a $10$, así que si puedo agregar $23$ $667$I reducir el problema de si un número de dos dígitos es divisible por $23$. $667+23=690$, de modo que el número de dos dígitos es $69$, y que obviamente es divisible por $23$. Por lo tanto,$667=23\times\text{something}$. Desde $69=23\times3$, tenemos $690=23\times30$, y esto es $23$ menos que eso, por lo $667=23\times29$, e $29$ es un número primo, así que hemos terminado. PERO uno comprueba el resultado mediante la multiplicación por otros métodos, y así me doy cuenta de que a mitad de camino entre el$23$$29$$26$, lo $23\times29=(26+3)(26-3)$. Factorización de una diferencia de dos cuadrados es algo que todo el mundo aprendido en el 7º grado (excepto aquellos que no....) y así es $26^2-3^2$. Sé que $26^2 = 676$, e $3^2 = 9$, y supongo que lo $676 - 9$ es? Así funciona. Y por supuesto que también puede hacerlo a través de la ley distributiva, la forma en que te enseñaron en el tercer grado.
La pregunta es: Si una de las figuras en cada instancia, lo que el más eficiente es, de entre todos los de la aritmética accesos directos y técnicas que pueden cruzar la mente en hacer esto, sería la de diez o quince segundos que se tarda en hacer todo lo anterior de repente se expande a más de tiempo que se necesitaría si sólo pesadamente a través del mismo por aplicación de lo prescrito algoritmos que usted aprendió en la infancia? A menudo en cuestión de segundos después de que yo haga algo como esto, creo que de dos o tres otros accesos directos que habría sido más rápido. Pero si me he parado a evaluar todas las posibilidades, me llevaría más tiempo de lo que acaba de hacer cosas como lo que he descrito anteriormente, y no pensar acerca de qué alternativas podría no haber ocurrido a mí. Así que la pregunta es si esta observación informal puede ser hecho preciso y demostrado.
Advertencia: Uno de los comentarios que suscita en mi mente la pregunta de si esto será ampliamente incomprendida. Yo soy NO preguntar si el uso de los accesos directos que vienen a la mente sobre la marcha es más rápido que el uso de los algoritmos que se les ha enseñado a su madre de la rodilla. Ya sé que es. De lo contrario no podría haber escrito lo que hice anteriormente. Lo que yo estoy preguntando es esto: Iba a tomar más tiempo para averiguar de qué manera es más rápido que usar lo que viene a la mente?
Otra aclaración: me dijo: "en diez o quince segundos". Sospecho que todo lo que he descrito anteriormente explícitamente probablemente me llevó menos de diez segundos, pero en realidad la eliminación de los números primos menos que 23 años antes de que probablemente me tomó más de dos veces ese tiempo.
