Notación Big O, algoritmos comunes de ordenamiento y búsqueda, y patrones de recursión evaluados en entrevistas técnicas y cursos universitarios.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- ¿Qué mide la notación Big O?
- Cómo crecen los requisitos de tiempo de ejecución o espacio de un algoritmo a medida que aumenta el tamaño de la entrada.
- Define la complejidad temporal O(1).
- Tiempo constante; el tiempo de ejecución no cambia sin importar el tamaño de la entrada.
- Define la complejidad temporal O(n).
- Tiempo lineal; el tiempo de ejecución crece proporcionalmente con el tamaño de la entrada n.
- Define la complejidad temporal O(log n).
- Tiempo logarítmico; el tiempo de ejecución crece con el logaritmo del tamaño de la entrada.
- Define la complejidad temporal O(n^2).
- Tiempo cuadrático; el tiempo de ejecución crece con el cuadrado del tamaño de la entrada.
- Define la complejidad temporal O(n log n).
- Tiempo linearítmico; el tiempo de ejecución es n multiplicado por el logaritmo de n.
- Define la complejidad temporal O(2^n).
- Tiempo exponencial; el tiempo de ejecución se duplica con cada incremento del tamaño de la entrada.
- ¿Cuál es la complejidad temporal de acceder a un elemento de un arreglo por índice?
- O(1), tiempo constante.
- ¿Cuál es la complejidad temporal de buscar un valor en un arreglo sin ordenar?
- O(n), tiempo lineal.
- ¿Cuál es la complejidad temporal de la búsqueda binaria en un arreglo ordenado?
- O(log n), tiempo logarítmico.
- ¿Qué debe cumplirse en un arreglo antes de poder usar la búsqueda binaria?
- El arreglo debe estar ordenado.
- ¿Cuál es la complejidad temporal de insertar un elemento al inicio de un arreglo?
- O(n), tiempo lineal.
- ¿Cuál es la complejidad temporal de añadir un elemento a un arreglo dinámico con capacidad disponible?
- O(1), tiempo constante amortizado.
- ¿Cuál es la complejidad temporal promedio de buscar en una tabla hash?
- O(1), tiempo constante con una buena función hash.
- ¿Cuál es la complejidad temporal de quicksort en el caso promedio?
- O(n log n), tiempo linearítmico.
FlashKeepers