Complejidad Algorítmica y Estructuras de Datos
Enviado por Chuletator online y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 3,37 KB
Acceso a la Cabeza y a la Cola
(Solo a la cabeza)
| Tipo de Lista | Inserción Cabeza | Inserción Cola | Borrado Cabeza | Borrado Cola | Búsqueda |
|---|---|---|---|---|---|
| Simple | Constante | Cte/Lineal | Constante | Lineal | Lineal |
| Doble | Constante | Cte/Lineal | Constante | Cte/Lineal | Lineal |
| Circular | Constante | Cte/Lineal | Constante | Lineal | Lineal |
| Circular Doble | Cte/Depende | Constante | Constante | Constante | Lineal |
| Vector | Lineal | Constante | Lineal | Constante | Lineal |
| ABB | Logarítmico | Logarítmico | Logarítmico | Logarítmico | Logarítmico |
Complejidad de Algoritmos de Ordenación
| Algoritmo | Mejor Caso | Peor Caso | Memoria Adicional |
|---|---|---|---|
| Inserción | n | N2 | No |
| Selección | N2 | N2 | No |
| HeapSort | n*log2(n) | n*log2(n) | No |
| MergeSort | n*log2(n) | n*log2(n) | Sí |
| QuickSort | n*log2(n) | N2 | No |
Comparativa de Estructuras de Datos
| Repetir Elementos | Elementos Ordenados | Estructura Interna | Coste Inserción | Coste Búsqueda | |
|---|---|---|---|---|---|
| TreeSet | No | Sí | Árbol Rojo-Negro | Logarítmica | Logarítmica |
| HashSet | No | No | Tabla Hash | Constante | Constante |
Distancia de Edición
Tenemos dos cadenas, y el objetivo es transformar una en la otra en el mínimo número de operaciones. Las operaciones que se utilizan pueden ser inserción, borrado y sustitución de símbolos (caracteres). La técnica que se utiliza para esto es la programación dinámica.
Algoritmos de Ordenación
- El algoritmo de ordenación QuickSort, basado en la técnica de divide y vencerás, tiene un coste O(n2) en el peor caso.
- El algoritmo MergeSort se basa en la técnica divide y vencerás.
- El algoritmo de ordenación por inserción tiene un coste lineal en el mejor caso.
- Los algoritmos de ordenación HeapSort y MergeSort tienen en común un coste O(nlog(n)) en el peor caso.
- Una versión mejorada del algoritmo de ordenación selección es el HeapSort.
Notación Big O
O(1) (const) ⊂ O(log(log n)) (sublog) ⊂ O(log n) (log) ⊂ O(loga>1(n)) (log) ⊂ O(√n) (sublineal) ⊂ O(n) (lineal) ⊂ O(n log n) (lineal-log) ⊂ O(n2) ... (polin) ⊂ O(na>2) (polin) ⊂ O(2n) (exponencial) ⊂ O(n!) (superexp) ⊂ O(nn) (superexp)
Complejidad de un Bucle 'for'
for = inicialización + veces * (condición cierto + cuerpo + incremento) + condición falsa