Existe un algoritmo de coste asintótico lineal, en el caso peor, para el problema de selección, es decir, para el cálculo del k-ésimo menor elemento (o estadístico de orden k) de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ). Os lo incluyo debajo, extraído del [...]
. El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(nlog 3) ( ≈ O(n1,59) ) aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de [...]