BrainTok
ENESIT

Estructuras de datos y algoritmos: Análisis asintótico y notación Big-O · Big-O, Omega grande y Theta grande

Cómo O, Ω y Θ acotan el crecimiento de un algoritmo, y cómo aplicarlas a ciclos, recursión y comparaciones reales.

Estructuras de datos y algoritmos · 30 preguntas

Prueba 3 preguntas

1. Formalmente, ¿qué significa que el tiempo de ejecución de un algoritmo sea O(n²)?

  1. Para n grande, crece como mucho como n²
  2. Para n grande, crece al menos como n²
  3. Para todo n, es exactamente proporcional a n²
Ver la respuesta

Respuesta: Para n grande, crece como mucho como n²

Big-O es una cota superior: existen constantes c y n₀ tales que el tiempo es como máximo c·n² para todo n ≥ n₀.

2. ¿Qué notación asintótica expresa una cota inferior de qué tan rápido crece una función?

  1. o pequeña (o)
  2. Omega grande (Ω)
  3. Theta grande (Θ)
Ver la respuesta

Respuesta: Omega grande (Ω)

f es Ω(g) cuando, para n grande, f(n) ≥ c·g(n) para alguna constante positiva c: f crece al menos tan rápido como g.

3. ¿Cuándo una función es Θ(n log n)?

  1. Cuando es igual a n log n más una constante
  2. Cuando n log n la acota solo por arriba
  3. Cuando n log n la acota por arriba y por abajo
Ver la respuesta

Respuesta: Cuando n log n la acota por arriba y por abajo

Θ es una cota ajustada: la función es a la vez O(n log n) y Ω(n log n), así que queda entre dos múltiplos constantes de n log n.

El resto del quiz, unas pocas preguntas a la vez

BrainTok te hace unas preguntas de quizzes como estos antes de abrir las apps que elijas, y tu tiempo de pantalla se vuelve aprendizaje. Para iPhone.

Únete a la beta

Más quizzes de Ingeniería en Sistemas y Computación