Lección 04: Análisis Algorítmico y Funciones de crecimiento

Conceptos

Big-O Notation: para suavisar la curva debe llevar se logaritmico.

Tipo de Big-O

Constante--> O(1) [sin ciclos]

Lineal, O(n) [un ciclos]

Otras: O(n^3), n*ln(n), ln(n)

Cuadrática, O(n^2) [dos ciclos]

Impacto CPU

Mover Memoria RAM cuesta 1 unidad de CPU

Todos los operadores (ALU) cuesta una unidad de CPU

Valor de uno (1) CPU

Asisgar una variable

todo operador *,+, /, %, etc.

operar un array [] :

invocar una metodo o propiedad de un objeto

retornar un valor

Algoritmo de Ordenamiento

Burbuja (n^2)

Selection n^2

Insertion n^2

QuickSort n*ln(n)

Algoritmo Busqueda

Secuencial - N

Binaria n*ln(n)

Alborea ln(n)

Hash - n*ln(n)

Recursidad

Lineal

No-Lineal

Caso Base, caso recurrente y factor de convergencia.

Consume mucha memoria y el caso base debe ser preciso y finito

Polinomio de Crecimiento. o Complejidad de un Algoritmo.

Momoria RAM

Depende de los Tipos De Datos.

Merge Sort se basa en RAM.

Tipos de Datos

int 32 bit

long 64 bit

short 16 bit

char 2 byte 16 bit

byte 8 bit

Un Algoritmo tiene RAM tipos de Datos*[n]

MergeSort (n*ln(n)

C++ Punteros a Funciones

void (*) (int A, int N) prototipo

vector<void (*) (int *, int)> Methods;

Methods.push_back(&QuickSort);

void compareSortDisplay2(int E, int N, void (SortMthd)(int*,int), string name ){ ... SortMthd(E, N); ..}