Estoy tratando de entender diferentes algoritmos de ordenación y su notación BigO. Supongamos que estoy usando la ordenación por inserción y tengo el peor caso:
6 | 5 | 4 | 3 | 2 | 1El número de comparaciones será $1 + 2 + 3 + 4 + 5 = 15$ o podemos escribirlo como
1 + 2 + 3 + ... + (n-1)También podemos utilizar la fórmula para calcular el número de comparaciones para esta secuencia:
n(n-1)/2Pero no me queda claro cómo convertirlo:
1 + 2 + 3 + ... + (n-1) --> n(n-1)/2¿Puede ayudar?
Escribe la secuencia dos veces, una de la manera "correcta" y otra al revés, y luego suma verticalmente: $$\begin{array}{cccccc} 1 & + & 2 & + & 3 & + & \ldots & + & (n-1) \\ (n-1) & + & (n-2) & + & (n-3) & + & \ldots & + & 1 \\ \hline n & + & n & + & n & + & \ldots & + & n \end{array}$$ Ahora, ¿cuál es la nueva suma? Bueno, hay $n-1$ " $n$ " para sumar. Así tenemos $n(n-1)$ como la nueva suma.
PERO, sabemos que la nueva suma es el doble de la anterior (después de todo, la hemos sumado dos veces). Así que divide la nueva suma entre dos para obtener la antigua: $$\frac{n(n-1)}{2}$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
