Esperamos que la posición del elemento aleatorio en la secuencia ordenada se distribuya uniformemente entre 0 y N-1, donde N es la longitud del conjunto de datos. Esto significa que hay al menos una probabilidad de 1/2 de que esté entre N / 4 y 3N / 4. Eso significa que al menos la mitad del tiempo, obtenemos un pivote que reduce el problema a no más de 3/4 del tamaño del problema anterior.
Cada selección de pivote y filtrado de los elementos por el pivote toma O (N) si quedan N elementos restantes. Con base en lo anterior, esperamos que el problema se reduzca a no más de 3/4 de su tamaño después de dos de estos pases O (N). Por lo tanto, obtenemos una relación de recurrencia de T (N) = T (3N / 4) + 2 * O (N) = T (3N / 4) + O (N), el último paso se justifica por el hecho de que las constantes pueden ser colapsó en la gran O.
Entonces, [matemáticas] T (N) = cN + T (\ frac {3} {4} N) = cN + c (\ frac {3} {4} N) + T (({\ frac {3} { 4}}) ^ 2 N) [/ matemáticas] [matemáticas]… = cN + c (\ frac {3} {4} N) + c (({\ frac {3} {4}}) ^ 2N) + … = CN (1 + \ frac {3} {4} + ({\ frac {3} {4}}) ^ 2 +…) = O (N) [/ matemáticas]
- Cómo encontrar las especificaciones de una computadora
- ¿Puede una máquina de Turing operar con un conjunto de instrucciones para todas las entradas y mostrar la respuesta correcta?
- ¿Cuáles son las principales diferencias entre el motor de búsqueda y la base de datos?
- ¿Cuál es el significado de "migas de pan" en la jerga de la base de datos?
- ¿Cómo la computadora puede calcular?
El último paso está justificado porque las series geométricas suman constantes de colapso constante y de gran O.
