TIPOS DE ALGORITMOS

Insertion Sort

Propiedades

•      estable
•      O (1) espacio extra
•      O (n2) comparaciones y swaps
•      Adaptación: O (n) el tiempo en que casi clasificado
•      Gastos generales muy bajos
  
  
  A pesar de que es uno de los algoritmos elementales de clasificación con O (n2) peor de los casos el tiempo, ordenación por inserción es el algoritmo de elección, ya sea cuando los datos se ordenan casi (porque es de adaptación) o cuando el tamaño del problema es pequeña (debido a que ha bajos costos).

 
 
 SELECTION SORT

 Propiedades

•      no es estable
•      (1) espacio extra
•       (n2) comparaciones
•       (n) los swaps
•      no de adaptación

 DESCRIPCIÓN
 Se puede concluir que la ordenación por selección nunca debe ser usado. No se adapta a los datos de cualquier manera, por lo que su tiempo de ejecución es siempre de segundo grado.

Sin embargo, una especie de selección tiene la propiedad de reducir al mínimo el número de intercambios. En aplicaciones donde el costo de los artículos de intercambio es alto, una especie de selección muy bien puede ser el algoritmo de elección.

 BUBBLE SORT

Propiedades

•      estable
•      O (1) espacio extra
•      O (n2) comparaciones y swaps
•      Adaptación: O (n) cuando casi clasificado

 
DESCRIPCIÓN

Especie de burbuja tiene muchas de las mismas propiedades que la ordenación por inserción, pero tiene sobrecarga ligeramente superior. En el caso de los datos de cerca de clasificar, ordenar burbuja toma O (n), pero requiere al menos 2 pasa a través de los datos (mientras que la ordenación por inserción requiere algo más parecido a un pase).




SHELL SHORT


propiedades

•      no es estable
•      O (1) espacio extra
•      O (n3 / 2) hora como se muestra (ver más abajo)
•      Adaptación: O (n · lg (n)) momento en que casi clasificados

DESCRIPCIÓN

La complejidad del tiempo peor de los casos de tipo concha depende de la secuencia de incremento. Para el 1 4 13 40 121 incrementos de ..., que es lo que se usa aquí, la complejidad en tiempo es O (n3 / 2). Para otros incrementos, la complejidad de tiempo se sabe que es O (n4 / 3) y hasta O (n · LG2 (n)). Ni estrechos límites superiores de la complejidad del tiempo ni la mejor secuencia de incremento se conocen.

Debido a que tipo de shell se basa en la ordenación por inserción, una especie de shell hereda las propiedades de adaptación tipo de inserción. El adapation no es tan dramático, porque la ordenación Shell requiere un paso a través de los datos por cada incremento, pero es significativo. Para la secuencia de incremento se muestra más arriba, hay log3 (n) se incrementa, por lo que la complejidad del tiempo para los datos de casi ordenada es O (n · log3 (n)).

Debido a su bajo costo operativo, de aplicación relativamente sencilla, las propiedades de adaptación, y sub-cuadrática complejidad de tiempo, tipo concha puede ser una alternativa viable a la O (n · lg (n)) algoritmos de ordenación para algunas aplicaciones cuando los datos a ordenar es no es muy grande.


MERGE SORT

 Propiedades

•      estable
•       (n) un espacio extra para las matrices (como se muestra)
•       (lg (n)) un espacio extra para listas enlazadas
•       (n · lg (n)) el tiempo
•      no de adaptación
•      No requiere acceso aleatorio a los datos

DESCRIPCIÓN

Tipo de mezcla es muy predecible. Hace entre 0,5 * lg (n) y LG (n) comparaciones por elemento, y entre los lg (n) y 1.5 * lg (n) los swaps de cada elemento. Los mínimos se obtienen de los datos ya están ordenados, los máximos se alcanzan, en promedio, para datos aleatorios. Si se utiliza Θ (n) un espacio extra no es de interés, y luego fusionar especie es una excelente opción: es fácil de implementar, y es la única estable O (n · lg (n)) algoritmo de ordenación. Tenga en cuenta que al ordenar las listas enlazadas, fusionar tipo sólo requiere Θ (lg (n)) el espacio extra (por repetición).

Tipo de combinación es el algoritmo de elección para una variedad de situaciones: cuando la estabilidad es necesaria, al ordenar las listas enlazadas, y cuando el acceso al azar es mucho más caro que el acceso secuencial (por ejemplo, la clasificación externa en la cinta).

No existen el tiempo lineal en lugar de combinar los algoritmos para el último paso del algoritmo, pero son costosos y complejos. La complejidad se justifica para aplicaciones como la clasificación externa cuando Θ (n) un espacio extra no está disponible.


HEAP SORT

Propiedades

•      no es estable
•      O (1) de espacio extra (véase el debate)
•      O (n · lg (n)) el tiempo
•      En realidad, no adaptativa

DESCRIPCIÓN

Ordenación por montículo es fácil de implementar, realiza una operación O (n · lg (n)) en lugar de ordenar, pero no es estable.

El primer bucle, el Θ (n) "heapify" fase, pone a la matriz en orden montón. El segundo bucle, el O (n · lg (n)) "sortdown" fase, en repetidas ocasiones extrae el máximo y restaura el orden montón.

La función de sumidero que está escrito de forma recursiva para mayor claridad. Así, como muestra, el código requiere Θ (lg (n)) un espacio para la pila de llamadas recursivas. Sin embargo, la recursión de cola en el lavabo () se convierte fácilmente en iteración, lo que da la O (1) espacio obligado.

Ambas fases son un poco de adaptación, aunque no de manera especialmente útil. En el caso de casi ordenados, la fase de heapify destruye el orden original. En el caso de invertir, la fase de heapify es lo más rápido posible ya que la matriz se inicia con el fin de montón, pero luego la fase de sortdown es típico. En el caso de algunas claves únicas, hay una cierta aceleración, pero no tanto como en una especie de shell o quicksort 3-way.


QUICK SORT


Propiedades

•      no es estable
•      O (lg (n)) espacio adicional (véase el debate)
•      O (n2), pero por lo general O (n · lg (n)) el tiempo
•      no de adaptación

DESCRIPCIÓN

Cuando cuidadosamente implementado, más o menos rápido es robusto y tiene bajos costos. Cuando una especie estable, no se necesita, más o menos rápido es un excelente tipo de propósito general - aunque la versión de partición de 3 vías siempre se debe utilizar en su lugar.

A más eficiente y robusto de 2 vías método de división se da en el Quicksort es óptima por Robert Sedgewick y Jon Bentley. La partición robusta produce recursividad equilibrada cuando hay muchos valores iguales al pivote, dando garantías probabilística de O (n · lg (n)) y el tiempo de O (lg (n)) espacio para todas las entradas.

Con ambos tipos sub-realiza de manera recursiva, más o menos rápida requiere O (n) más espacio para la pila de recursión en el peor de los casos cuando la recursividad no es equilibrada. Esto es muy poco probable que ocurra, pero puede ser evitado por la clasificación de pequeñas sub-conjunto recursivamente primero y el segundo sub-array tipo es una llamada recursiva de cola, que se puede hacer con la iteración en su lugar. Con esta optimización, el algoritmo utiliza O (lg (n)) espacio extra en el peor de los casos.



QUICK SORT 3

Propiedades

•      no es estable
•      O (lg (n)) espacio extra
•      O (n2), pero por lo general O (n · lg (n)) el tiempo
•      Adaptación: O (n) tiempo en O (1) claves únicas

DESCRIPCIÓN

La variación de la partición de 3 vías de tipo rápido tiene arriba un poco mayor en comparación con la versión estándar de partición de 2 vías. Ambos tienen el mismo mejor, típico, y en el peor caso de los límites de tiempo, pero esta versión es altamente adaptable en el caso muy común de la clasificación con algunas claves únicas.

Cuando la estabilidad no es necesario, de 3 vías tipo de partición rápido es el algoritmo de propósito general de clasificación de la elección.

En resumen el algoritmo mas rápido es el quick sort 3 aunque no es muy estable, despues le sigue el heap y quick, y por ultimo el de inserción

REFERENCIAS:

http://www.sorting-algorithms.com/
http://en.wikipedia.org/wiki/Algorithm

ITERACIÓN

Estructura iterativa

Un bucle iterativo o iteración de una secuencia de instrucciones, hace que se repita su ejecución mientras se cumpla una condición, el número de iteraciones normalmente está determinado por el cambio en la condición dentro del mismo bucle, aunque puede ser forzado o explícito por otra condición.

Esta instrucción tiene tres palabras reservadas WHILE, DO y LOOP.

• DO WHILE: señala el comienzo del bucle ("haga mientras") y después de estas palabras se espera la condición lógica de repetición, si la condición es verdadera pasa el control al cuerpo del bucle, en caso contrario el flujo salta directamente al final de la estructura, saliendo de la misma.
• LOOP: señala el final del cuerpo de la estructura de bucle.

El bucle mientras, se repite mientras la condición sea verdadera, esta condición se comprueba o chequea antes de ingresar al cuerpo del bucle, por lo que el mismo puede que no se ejecute nunca (cuando la condición es falsa desde un principio) o bien que se repita tantas veces como resulte y mientras la condición sea cierta.
En el ejemplo se tienen definidas dos variables a y b, que al iniciarse el bucle contienen los valores a=0 y b=7.
La condición del bucle es b > a.

Si a=0 y b=7. la condición es verdadera, en el cuerpo del bucle se escribe el valor de a en pantalla y luego se incrementa esa variable en una unidad. Entonces pasa a ser a=1 y b=7.

... (se repite la secuencia)

...

Cuando a=6 y b=7. la condición sigue siendo verdadera, se escribe el valor de a en pantalla y se incrementa en una unidad.

Cuando se llega a que a=7 y b=7. Entonces la condición ya resulta falsa y la instrucción WHILE finaliza, saliendo por LOOP.

La salida por pantalla de este ejemplo es 0 1 2 3 4 5 6, y se iteró 7 veces.

 

El lenguaje utilizado en el ejemplo (BASIC), además de tener otras del tipo iterativas, permite utilizar la misma estructura indicada, pero de la siguiente forma:

a= 0
   b= 7
   WHILE b > a
      PRINT a
      a= a + 1
   WEND

 

 REFERENCIAS:

 es.wikipedia.org/wiki/Iteración

http://es.wikipedia.org/wiki/Programaci%C3%B3n_estructurada

Recursión

es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin
En programación, una función es recursiva cuando se llama a sí misma.

Uno de los ejemplos más clásicos es el factorial de un número. Intenta seguir la explicación razonando cada paso. Para cualquier entero positivo N, el factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los enteros menor a él:

• 1! = 1
• 2! = 1 x 2 = 2
• 3! = 1 x 2 x 3 = 6
• 4! = 1 x 2 x 3 x 4 = 24
• 5! = 1 x 2 x 3 x 4 x 5 = 120
• 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720

Se puede ver que el factorial de cada número incluye el factorial de todos los números anteriores a él. Lo escrito en corchetes rectos a continuación es una referencia, no a nivel matemático:
“2!” es “1[1!] x 2″
“3!” es “(1 x 2)[2!] x 3″
Y así sucesivamente. Para cualquier entero N mayor a 1, podemos decir que el factorial de N es igual al factorial del número anterior a N multiplicado por N. La fórmula N! = (N-1)! x N. Vuelve a la lista de factoriales de 1 a 6. Busca en cada caso los términos que son factorial del número anterior para darte cuenta. Entonces se podria decir que una buena practica es encontrar el factor en el resultado que se repite.

Pasando ésto a función en C, podemos hacer una función a la que le pasamos un número, y nos devuelve el factorial:

 

Ahí tenemos nuestra primera función recursiva. Pero si compilamos el código y ejecutamos el programa, obtenemos una hermosa violación de segmento.

El problema es que la función definida arriba no termina nunca, va a seguir restándole 1 a N por siempre. Siempre vamos a poder restarle 1 a cualquier n, por lo que la función va a seguir ejecutándose a sí misma por siempre. Además, para cualquier número positivo, factorial de n va a devolver 0, porque cualquier multiplicación con 0 como término devuelve 0. Y restarle 1 recursivamente a cualquier entero positivo, eventualmente dará cero.
Para que la función recursiva esté completa, además de llamarse a sí misma, necesita una forma de finalizar, una condición.

Por definición, el factorial de 1 es 1 (1!=1) así como el factorial de 0 (0!=1)también es 1. Por lo que podemos implementar ésta condición para que la función no sea interminable.
Así, la definición de la función consta de la recursiva que se llama a sí misma, y la condición para detenerse.

O con un while:

 

Y bueno, este fue mi intento por explicar qué es la recursividad en la programación y cómo funciona con un ejemplo. Otro buen ejemplo es la serie de Fibonacci, pero ésta da para un estudio más a fondo, ya que tiene bastantes cosas interesantes. También es interesante la Torre de Hanoi, resulta bastante interesante y clásico a la hora de aplicar recursividad.

REFERENCIAS:

http://www.algoritmia.net/articles.php?id=11

http://es.wikipedia.org/wiki/Recursi%C3%B3n

http://picandocodigo.net/2008/recursividad-en-programacion/

El logaritmo de un número, en una base dada, es el exponente al cual se debe elevar la base para obtener el número.

Siendo a la base, x el número e y el logaritmo.

TIPOS DE LOGARITMOS

Los logaritmos decimales o vulgares son los que tienen base 10. Se representan por log (x).

Los logaritmos naturales o logaritmos neperianos son los que tienen base e. Se representan por ln (x) o L(x).

Los logaritmos neperianios deben su nombre a su descubridor John Neper y fueron los primeros en ser utilizados.

Operaciones con logaritmos

Logaritmo de una multiplicación

1El logaritmo de una multiplicación es igual a lasuma de los logaritmos de los factores.

Logaritmo de una división

2 El logaritmo de un cociente es igual al logaritmodel dividendo menos el logaritmo del divisor.

Logaritmo de una potencia

3El logaritmo de una potencia es igual al productodel exponente por el logaritmo de la base.

Logaritmo de una raíz

4El logaritmo de una raíz es igual al cociente entre el logaritmo del radicando y el índice de la raíz.

5Cambio de base:

ME base en la siguiente información para darles a conocer lo mas importante que hay que 

saber de los LOGARITMOS

http://es.wikipedia.org/wiki/Logaritmo

http://www.vitutor.net/1/12.html

Ejercicio que hicimos en clase

Bueno pues este ejercicio lo hicimos en clase, y estábamos  comparando gráficas, que según
su función, y su comportamiento en la gráfica, veríamos cual de todas es la que incrementa mas rápidamente

Los valores de la recta en X eran: 1,2,4,8,16,32,64,128,256
Nuestras ecuaciones fueron:
 y1= log x
y2= 2^x

Como lo pueden ver claramente en esta imagen la función de y2 incrementa de una forma mas rápida.
Y con esto podemos concluir, que la gráfica de una función logarítmica, no es mayor a la de una función exponencial.