Algoritmia básica (AB) » Sin categoría http://webdiis.unizar.es/asignaturas/AB El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante Thu, 10 Feb 2022 08:44:19 +0000 en hourly 1 http://wordpress.org/?v=3.1.4 Cálculo de la mediana en tiempo lineal http://webdiis.unizar.es/asignaturas/AB/?p=2086 http://webdiis.unizar.es/asignaturas/AB/?p=2086#comments Tue, 14 Mar 2017 15:00:17 +0000 Javier Campos http://webdiis.unizar.es/asignaturas/AB/?p=2086 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 libro Introducion to Algorithms, de Cormen, Leiserson, Rivest y Stein.

Una vez se dispone de un algoritmo de coste lineal (caso peor) para el cálculo de la mediana, existe una modificación del algoritmo quicksort que tiene coste O(n logn) en el caso peor. Consiste en elegir la mediana como el pivote que se utiliza para la partición del vector en dos trozos, en cada llamada recursiva del quicksort.

]]> http://webdiis.unizar.es/asignaturas/AB/?feed=rss2&p=2086 0