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); ..}