¿Qué clase de algoritmo tienen las personas que tienen un análisis de complejidad asombroso (difícil, extraño) en términos de ambos? ¿Orencia resultante y singularidad en la forma en que se analizan?Algoritmos para Big O Analysis
La complejidad polinomial no determinista obtiene mi voto, especialmente con la posibilidad (que se considera poco probable) de que pueda ser el mismo polinomio. En el mismo sentido, cualquier cosa que pueda beneficiarse teóricamente de la computación cuántica (N.B. este conjunto no es de ninguna manera todos los algoritmos).
La otra que obtendría mi voto sería operaciones matemáticas comunes sobre números de precisión arbitraria: aquí es donde debe considerar cosas como la multiplicación de números grandes es más costoso que la multiplicación de los pequeños. Hay un montón de análisis de esto en Knuth (que no debería ser noticia para nadie). El método de Karatsuba es bastante limpio: corte los dos factores por la mitad por dígito (A1; A2) (B1; B2) y multiplique A1 B1, A1 B2, A2 B1, A2 B2 por separado, y luego combine los resultados. Recurse si se desea ...
El método de Karatsuba es ingenioso, esto es cierto. Sin embargo, dado que una transformada rápida de Fourier realiza una convolución, puede utilizarse para realizar las multiplicaciones más rápidas conocidas, suponiendo que los números son lo suficientemente grandes como para justificar el agravamiento de escribir una FFT de tamaño de entrada mixto y sintonizarla. –
Hmm, tendré que buscarlo. ¿Qué tan precisos deben ser los componentes para garantizar una multiplicación de enteros precisa? – Edmund
Según tengo entendido, simplemente necesita la precisión suficiente para mantener el número final. Aunque la técnica de multiplicación de FFT también se puede usar en tipos enteros directamente y siempre hay respuestas precisas. No tengo mi copia de Knuth aquí, pero creo que menciona la técnica y la repasa. –
Este es un poco simple, pero Comb Sort me hace pensar un poco.
http://en.wikipedia.org/wiki/Comb_sort
Es un algoritmo tan simple en su mayor parte se lee como una burbuja demasiado complicado especie, pero es O (n * Log [n]). Me parece algo impresionante.
La plétora de Algoritmos para transformaciones rápidas de Fourier también son impresionantes, la matemática que prueba su validez es tremenda y fue divertido intentar probar algunos por mi cuenta.
http://en.wikipedia.org/wiki/Fast_Fourier_transform
puedo bastante entender fácilmente la raíz primordial, radix primer múltiple, y los algoritmos de raíz mixta pero que trabaja en conjuntos cuyo tamaño son primos es bastante fría.
tengo (bastante) algunos ejemplos:
El análisis de búsqueda ordenado en 2D es bastante interesante. Tiene una matriz numérica bidimensional de números NxN donde cada fila se ordena de izquierda a derecha y cada columna se ordena de arriba hacia abajo. La tarea es encontrar un número particular en la matriz.
El algoritmo recursivo: elegir el elemento en el medio, compararlo con el número objetivo, descartar un cuarto de la matriz (dependiendo del resultado de la comparación), aplicar recursivamente a los restantes 3 trimestres es bastante interesante de analizar.
Shell sort. Hay toneladas de variantes con varios incrementos, la mayoría de los cuales no tienen ningún beneficio excepto para hacer el complexity analysis simpler.
¿Es eso un algoritmo? – shoosh
@p Esta respuesta probablemente esté bien, aunque solo sea de enlace. La "función de Ackermann" es suficiente para encontrarla en Internet y la pregunta, que probablemente esté fuera del tema, solo está solicitando algoritmos, no explicaciones. – royhowie