|
Título: Ordenación: método de la burbuja Publicado por: mvk en 11 Noviembre 2012, 19:16 pm Hi! Estoy programando en C, pero pongo la duda en está sección, ya que pienso que es más generica que de un lenguaje en particular.
Me encuentro con que en un análisis de las comparaciones que hay que hacer se tiene: caso más desfavorable: (n-1)+(n-2)+...+2+1 = (n-1)(n/2) El sacar (n-1)+(n-2)+...+2+1 lo entiendo pero, ¿Como se llega a la expresión (n-1)(n/2) ? Supongo que es una sucesión pero no llego a esa expresión :-\ Agradezco toda ayuda que me podáis brindar. Título: Re: Ordenación: método de la burbuja Publicado por: [Case] en 11 Noviembre 2012, 20:28 pm Es facil de ver una vez teniendo la idea de donde surgio.
Usare un ejemplo, desde el 1 al 100. En este caso n = 100. Ahora si te das cuenta, 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101. Asi hasta 50 + 51 = 101. n/2 es el numero de veces que sumamos 101, que es 50 en este caso. Y n + 1 es por que la suma de i + n - (i - 1) = n + 1 con i desde 0 hasta n Que es 101. Esto nos da la formula (n + 1)(n/2) = n + (n-1) + .. + 2 + 1 Por ultimo y el paso simple. Dado que tu lo que quieres es demostrar la suma desde 0 hasta n - 1, solamente nos falta restar n a la formula (n +1)(n/2). (n +1)(n/2) - n = (n^2 + n)/2 - 2n/2 = (n^2-n)/2 = (n-1)(n/2) Y de ahi sale, la demostracion formal debe de salir por inducción sobre n. Título: Re: Ordenación: método de la burbuja Publicado por: mvk en 12 Noviembre 2012, 01:11 am Hola Case, me he quedado así :o La verdad es que esto demuestra que estoy muy pez todavía. Lo de n/2 partiendo de 100+1, ok, pero eso de i + n - (i - 1) ya me he perdido, no entiendo que relación tiene con lo demás :(
Gracias por la paciencia Título: Re: Ordenación: método de la burbuja Publicado por: [Case] en 12 Noviembre 2012, 03:56 am Si perdo, ahi no lo explique bien.
Mira La serie en si es: Desde el i = 1 hasta i = n ∑i Que es: 1 + 2 + 3 + ... + n. Entonces lo que hago es cambiar el orden, en lugar de; 1 +2 + ... + n lo pongo así: [1 + n] + [2 + n - 1] + [3 + n - 2] + ... + [(n/2) + (n/2 + 1)] Si te das cuenta cada numero entre corchetes siempre da n + 1, en el caso del ejemplo siempre da 101 = 100 + 1. Y el numero de veces que sumaste n + 1 fue n/2. Por lo tanto queda (n + 1)(n/2). Lo demas es seguir la demostracion que te habia puesto. Título: Re: Ordenación: método de la burbuja Publicado por: mvk en 12 Noviembre 2012, 12:48 pm La serie pones que es sumatorio de i, pero yo hasta donde entiendo, tengo:
(n-1)+(n-2) + (n-3) +... + 2 + 1 Con lo que aquí ya me pierdo. Y luego, la serie 1 + 2 + ... + n, la conviertes en sumatorios de (n+1), pero sumar (n+1) + (n+1) + (n + 1) +... no es lo mismo que ir 1 + 2 + ... + n. Puff que lio, voy a darte mucha berra, pero es que tío, no me entra en la almendra. Título: Re: Ordenación: método de la burbuja Publicado por: mvk en 13 Noviembre 2012, 00:08 am Soy un boludo, por fin lo entendí!!!!!!
Gracias otra vez, Case. xau |