⏱️

Notación Big O

44 cards · 🇺🇸 English → 🇪🇸 Español

Análisis de la complejidad temporal y espacial de algoritmos y operaciones comunes.

Study all 44 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10

Question

Big O notation

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

1Big O notation
Una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende a infinito, utilizada para clasificar algoritmos según cómo crecen su tiempo de ejecución o sus requisitos de espacio a medida que aumenta el tamaño de la entrada
2Letter 'O'
Ordnung (alemán para 'orden'), que significa el orden de aproximación
3F(n) = O(g(n))
La función f está acotada superiormente por g (salvo un factor constante) de forma asintótica
4O(1) complexity
Tiempo constante: el algoritmo tarda lo mismo sin importar el tamaño de la entrada
5O(log n) complexity
Tiempo logarítmico: típico de algoritmos que dividen el problema a la mitad en cada paso (por ejemplo, la búsqueda binaria)
6O(n) complexity
Tiempo lineal: el tiempo de ejecución del algoritmo crece linealmente con el tamaño de la entrada
7O(n log n) complexity
Tiempo linearítmico o cuasilineal: típico de algoritmos de ordenamiento eficientes basados en comparación, como el merge sort y el heapsort
8O(2ⁿ) complexity
Tiempo exponencial: el tiempo de ejecución se duplica con cada elemento adicional de entrada
9Little-o notation
Una notación donde f(n) = o(g(n)) significa que f crece mucho más lento que g de forma asintótica
10Big Omega (Ω) notation
Una notación que proporciona una cota inferior sobre la tasa de crecimiento de una función (f está acotada inferiormente por g)
11Big Theta (Θ) notation
Una notación que significa que f está acotada por g tanto por arriba como por abajo (cota ajustada); f y g tienen el mismo orden de crecimiento
12F(n) ~ g(n)
Equivalencia asintótica: f es igual a g de forma asintótica (la razón f/g tiende a 1)
13Complexity of finding an item in a sorted array with binary search
O(log n)
14Complexity of finding an item in an unsorted list with linear search
O(n)
15Best possible time complexity for comparison-based sorting
O(n log n) en el caso promedio
16Time complexity of quicksort in the average case
O(n log n)
17Worst-case time complexity of quicksort
O(n²)
18Time complexity of merge sort
O(n log n) en todos los casos (mejor, promedio y peor)
19Time complexity of bubble sort
O(n²) en el peor caso y en el caso promedio, O(n) en el mejor caso (ya ordenado)
20Time complexity of insertion sort
O(n²) en el peor caso y en el caso promedio, O(n) en el mejor caso
21Space complexity of an algorithm
La cantidad de espacio de memoria adicional que requiere el algoritmo en función del tamaño de la entrada
22'in-place'
Un algoritmo que requiere solo O(1) u O(log n) de espacio adicional además de la entrada
23Amortized time complexity
El tiempo promedio por operación a lo largo de una secuencia de operaciones en el peor caso
24Inverse Ackermann function's complexity
O(α(n)), que crece extremadamente lento, prácticamente constante para fines prácticos (se usa en operaciones de conjuntos disjuntos)
25Polylogarithmic time
O((log n)^k) para alguna constante k: más lento que el logarítmico pero más rápido que cualquier polinomio
26Superpolynomial function
Una función que crece más rápido que n^c para cualquier constante c
27Subexponential function
Una función que crece más lento que c^n para cualquier constante c > 1
28Can you ignore constant factors in Big O notation?
Sí, las constantes se omiten: O(5n) = O(n), O(3n²) = O(n²)
29Can you drop lower-order terms in Big O notation?
Sí: O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)
30Is Big O notation an equality or an inequality?
En realidad es una desigualdad (cota superior) a pesar de usar el símbolo =, que representa 'es elemento de' un conjunto