Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de ordenameitno INSERTION, MERGE EVALUATION, Imagen de…
Algoritmos de ordenameitno
INSERTION, MERGE
EVALUATION
2.1 SORT ALGORITHM
aLGORITMOS DE ORDENAMIENTO
INSERTION SORT
MERGE SORT
DE mezcla
Divide and conquer.
Divide in 2
Conquer, solve
Mix
CASES
BETTER
O(nlogn)
WORSE
O(nlogn)
avergae
O(nlogn)
mas rapido para grandes cantidades
bUBLE SORT
Bubble
worst case (n^2)
o((n^2))
best case
(n^2) o n
Que este ordenado
O(n)
pROMEDIO
T (n)
Quick sort
merjoe caso
Caso promedio
Peor caso
2.2 ANALYSUZNG ALGOTRITHS
eVALUATION
How to measure?
Efficiencia
Notation BIG O
Spacial Complexity
RAM Model (Random-Access Machine).
La porci[on de memoria que requieren
COmplejidad Temporal
Common notation
Del m[al lento a m[as r[spido
Constante
O(1)
interchange of variables (a,b) = (b,a)
Assembler can do it.
Logarítmico
O(log n)
Crece muy lentamente
Lineal
O(n)
O(n) -- Linear space
Copy an array or create a list of greetings
Crece proporcionakmente
Linealitmico
O(n log n)
Un poco m[as rapido que el lineal
Cuadrático
O(n*2)
Crece al cuadrado de la entrada
Exponencial
0(2**n)
Crece muy r[apidamente
Factorial
O(n!)
Crece extremadamente rapido
Cual es m[as rapido
We don’t use a clock. Instead, we count the number of steps the algorithm takes. The more steps, the slower it is. The number of steps usually depends on the size of the input (n)
Worst Case (Slowest) → Θ(n²):
If the numbers are in reverse order, the algorithm works the hardest.
It has to compare each number with all the previous ones.
Takes about n² steps (really slow for large n).
Best Case (Fastest) → Θ(n):
If the numbers are already sorted, the algorithm barely does any work.
Takes about n steps (much faster).
Average Case → Θ(n²):
If the numbers are randomly arranged, the algorithm still does a lot of work.
Takes about n² steps like the worst case.
Invariantes de Bucle Loop invariants
Propiedad par ademostrar que un algortimo es correcto
Comparaciones entre algoritmos
Se puede graficar en python
T(n)
O(n)
Θ(n)
Ω(n)
