Sin nada

Algoritmo Lineal - Aleatoriedad - Presentation Transcript
Algoritmos para generar números aleatorios Algoritmo lineal
Fue propuesto por D.H. Lehmer en 1951.
Según Law y Kelton, este algoritmo hasido el mas usado.
Donde X 0 es la semilla
a es constante multiplicativa
c es constante aditiva
m es modulo
X 0 > 0, a > 0, c > 0, m > 0 y todos deben ser enteros
i = 1,2,3,4…,n

Órdenes deComplejidad

La familia O(f(n)) define un Orden de Complejidad. Elegiremos como representante de este Orden de Complejidad a la función f(n) más sencilla perteneciente a esta familia.
Las funciones decomplejidad algorítmica más habituales en las cuales el único factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son:

O(1)

Orden constanteO(log n)

Orden logarítmico

O(n)

Orden lineal

O(n log n)

Orden cuasi-lineal

O(n2)

Orden cuadrático

O(n3)

Orden cúbico

O(na)

Orden polinómico

O(2n)

Ordenexponencial

O(n!)

Orden factorial

Se identifica una Jerarquía de Ordenes de Complejidad que coincide con el orden de la tabla mostrada; jerarquía en el sentido de que cada orden de complejidadinferior tiene a las superiores como subconjuntos.
O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.
O(log n): Complejidad logarítmica. Esta suele aparecer en determinadosalgoritmos con iteración o recursión no estructural, ejemplo la búsqueda binaria.
O(n): Complejidad lineal. Es una complejidad buena y también muy usual. Aparece en la evaluación de bucles simples siempreque la complejidad de las instrucciones interiores sea constante.
O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenaciónquicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.
O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente...