Complejidad Algorítmica

Análisis y cálculo de la eficiencia de algoritmos, notación Big O, complejidad temporal y espacial, y comparación de algoritmos según su rendimiento

Category
Computer Programming
Level
intermediate
Languages
es → es
Cards
50
Markdown
Complejidad Algorítmica (.md)

Flashcards (50)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1¿Cuál es la complejidad temporal del algoritmo de ordenación por inserción?O(n^2) en el peor caso, O(n) en el mejor caso.
2¿Qué es un algoritmo de búsqueda?Es un algoritmo que encuentra la posición de un elemento en una estructura de datos.
3¿Qué es un algoritmo de ordenación por selección?Es un algoritmo que divide la lista en dos partes: la parte ordenada y la parte desordenada, seleccionando el mínimo de la parte desordenada.
4¿Qué es la complejidad en el peor caso?Es la máxima cantidad de tiempo o espacio que un algoritmo puede requerir para una entrada dada.
5¿Qué es la complejidad de un algoritmo de búsqueda en profundidad (DFS)?O(V + E), donde V es el número de vértices y E es el número de aristas en un grafo.
6¿Qué es un algoritmo voraz?Es un algoritmo que toma decisiones óptimas en cada paso con la esperanza de encontrar una solución óptima global.
7¿Cuál es la complejidad de búsqueda en un árbol binario de búsqueda balanceado?O(log n), donde n es el número de nodos.
8¿Cuál es la complejidad de inserción en un árbol rojo-negro?O(log n), donde n es el número de nodos.
9¿Qué es un algoritmo recursivo?Es un algoritmo que se llama a sí mismo para resolver subproblemas más pequeños del mismo tipo.
10¿Cuál es la complejidad temporal de un algoritmo de búsqueda binaria?O(log n), donde n es el número de elementos en la lista ordenada.
11¿Qué es la notación Ω?Es una notación que describe el límite inferior de la complejidad de un algoritmo, indicando el mejor caso.
12¿Qué es un algoritmo de Dijkstra?Es un algoritmo para encontrar el camino más corto desde un nodo a todos los demás nodos en un grafo ponderado.
13¿Cuál es la complejidad temporal del algoritmo de Floyd-Warshall?O(V^3), donde V es el número de vértices.
14¿Cómo se calcula la complejidad de un algoritmo recursivo?Se utiliza la relación de recurrencia para expresar la complejidad en términos de la complejidad de sus subproblemas.
15¿Qué mide la complejidad espacial?Mide la cantidad de memoria que utiliza un algoritmo en función del tamaño de la entrada.
16¿Cuál es la complejidad de un algoritmo de backtracking en el problema de las N reinas?O(N!), donde N es el número de reinas.
17¿Qué es la complejidad amortizada?Es un análisis que promedia el tiempo de ejecución de una operación a lo largo de una serie de operaciones.
18¿Cuál es la complejidad temporal del algoritmo de ordenación por selección?O(n^2) en todos los casos.
19¿Qué es la complejidad algorítmica?Es una medida que describe el rendimiento de un algoritmo en términos de tiempo y espacio en función del tamaño de la entrada.
20¿Qué mide la complejidad temporal?Mide el tiempo que tarda un algoritmo en completarse en función del tamaño de la entrada.
21¿Qué es un algoritmo de ordenación?Es un algoritmo que organiza los elementos de una lista en un orden específico, como ascendente o descendente.
22¿Qué significa O(n^2)?Indica que el tiempo de ejecución del algoritmo crece cuadráticamente con el tamaño de la entrada.
23¿Qué es un árbol binario de búsqueda?Es una estructura de datos en la que cada nodo tiene como máximo dos hijos y se organiza de tal manera que el hijo izquierdo es menor y el derecho es mayor que el nodo padre.
24¿Cuál es la complejidad temporal de un algoritmo de búsqueda lineal?O(n), donde n es el número de elementos en la lista.
25¿Cuál es la complejidad temporal del algoritmo de Dijkstra?O((V + E) log V) utilizando una cola de prioridad.
26¿Cuál es la complejidad temporal del algoritmo de ordenación rápida (Quicksort)?O(n log n) en el promedio, O(n^2) en el peor caso.
27¿Qué es la complejidad de un algoritmo de fusión (Merge Sort)?O(n log n) en todos los casos.
28¿Qué es un algoritmo de Floyd-Warshall?Es un algoritmo para encontrar los caminos más cortos entre todos los pares de nodos en un grafo.
29¿Qué significa O(1)?Indica que el tiempo de ejecución del algoritmo es constante, independientemente del tamaño de la entrada.
30¿Qué es un heap?Es una estructura de datos que satisface la propiedad del heap, donde el valor de cada nodo es mayor o menor que sus hijos.
31¿Qué es la colisión en hashing?Es cuando dos entradas diferentes producen el mismo valor hash.
32¿Cuál es la complejidad de búsqueda en un árbol AVL?O(log n), donde n es el número de nodos.
33¿Qué es un grafo?Es una estructura compuesta por nodos (vértices) y conexiones entre ellos (aristas).
34¿Cuál es la complejidad temporal de la programación dinámica en el problema de la mochila?O(nW), donde n es el número de elementos y W es la capacidad de la mochila.
35¿Qué es un árbol AVL?Es un árbol binario de búsqueda balanceado que mantiene su altura logarítmica mediante rotaciones.
36¿Qué es la complejidad promedio?Es la medida de la complejidad de un algoritmo considerando todas las posibles entradas y su probabilidad.
37¿Qué es la complejidad de un algoritmo de búsqueda en amplitud (BFS)?O(V + E), similar a DFS, ya que también explora todos los vértices y aristas.
38¿Qué es un ciclo en un grafo?Es un camino que comienza y termina en el mismo nodo sin repetir aristas.
39¿Cuál es la complejidad de insertar un elemento en un heap?O(log n), donde n es el número de elementos en el heap.
40¿Qué es la programación dinámica?Es un enfoque para resolver problemas complejos dividiéndolos en subproblemas más simples y almacenando sus soluciones.
41¿Cuál es la complejidad temporal del algoritmo de Kruskal para encontrar el árbol de expansión mínima?O(E log E), donde E es el número de aristas.
42¿Qué es la notación Θ?Es una notación que describe el límite superior e inferior de la complejidad de un algoritmo, proporcionando una descripción más precisa que O.
43¿Qué es un algoritmo de backtracking?Es un enfoque que prueba todas las soluciones posibles y retrocede cuando encuentra una solución no válida.
44¿Qué es un algoritmo de ordenación por inserción?Es un algoritmo que construye una lista ordenada insertando elementos uno a uno en su posición correcta.
45¿Qué es un árbol rojo-negro?Es un tipo de árbol binario de búsqueda balanceado que garantiza que la longitud del camino más largo no sea más del doble que la del más corto.
46¿Cuál es la complejidad temporal del algoritmo de ordenación por burbuja?O(n^2) en el peor y promedio de los casos.
47¿Qué es la notación Big O?Es una notación matemática que describe el comportamiento asintótico de la complejidad de un algoritmo, enfocándose en el peor caso.
48¿Qué es un algoritmo de hashing?Es un algoritmo que convierte una entrada en un valor de longitud fija, utilizado para acceder a datos de manera eficiente.
49¿Qué es la complejidad de un algoritmo de búsqueda binaria en un arreglo ordenado?O(log n), donde n es el número de elementos en el arreglo.
50¿Qué es la complejidad de un algoritmo de búsqueda secuencial?O(n), donde n es el número de elementos en la lista.